Given an array of n distinct and positive elements, the task is to find pair whose sum already exists in given array.
Examples :
Input : arr[] = {2, 8, 7, 1, 5};
Output : 2 5
7 1
Input : arr[] = {7, 8, 5, 9, 11};
Output : Not Exist
A Naive Approach is to run three loops to find pair whose sum exists in array.
C++
// A simple C++ program to find pair whose sum // already exists in array #include <bits/stdc++.h> using namespace std; // Function to find pair whose sum exists in arr[] void findPair(int arr[], int n) { bool found = false; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = 0; k < n; k++) { if (arr[i] + arr[j] == arr[k]) { cout << arr[i] << " " << arr[j] << endl; found = true; } } } } if (found == false) cout << "Not exist" << endl; } // Driven code int main() { int arr[] = { 10, 4, 8, 13, 5 }; int n = sizeof(arr) / sizeof(arr[0]); findPair(arr, n); return 0; } |
Java
// A simple Java program to find // pair whose sum already exists // in array import java.io.*; public class GFG { // Function to find pair whose // sum exists in arr[] static void findPair(int[] arr, int n) { boolean found = false; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = 0; k < n; k++) { if (arr[i] + arr[j] == arr[k]) { System.out.println(arr[i] + " " + arr[j]); found = true; } } } } if (found == false) System.out.println("Not exist"); } // Driver code static public void main(String[] args) { int[] arr = {10, 4, 8, 13, 5}; int n = arr.length; findPair(arr, n); } } // This code is contributed by vt_m. |
Python3
# A simple python program to find pair # whose sum already exists in array # Function to find pair whose sum # exists in arr[] def findPair(arr, n): found = False for i in range(0, n): for j in range(i + 1, n): for k in range(0, n): if (arr[i] + arr[j] == arr[k]): print(arr[i], arr[j]) found = True if (found == False): print("Not exist") # Driver code if __name__ == '__main__': arr = [ 10, 4, 8, 13, 5 ] n = len(arr) findPair(arr, n) # This code contributed by 29AjayKumar |
C#
// A simple C# program to find // pair whose sum already exists // in array using System; public class GFG { // Function to find pair whose // sum exists in arr[] static void findPair(int[] arr, int n) { bool found = false; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = 0; k < n; k++) { if (arr[i] + arr[j] == arr[k]) { Console.WriteLine(arr[i] + " " + arr[j]); found = true; } } } } if (found == false) Console.WriteLine("Not exist"); } // Driver code static public void Main(String []args) { int[] arr = {10, 4, 8, 13, 5}; int n = arr.Length; findPair(arr, n); } } // This code is contributed by vt_m. |
PHP
<?php // A simple php program to // find pair whose sum // already exists in array // Function to find pair whose // sum exists in arr[] function findPair($arr, $n) { $found = false; for ($i = 0; $i < $n; $i++) { for ($j = $i + 1; $j < $n; $j++) { for ($k = 0; $k < $n; $k++) { if ($arr[$i] + $arr[$j] == $arr[$k]) { echo $arr[$i] , " " , $arr[$j] ; $found = true; } } } } if ($found == false) echo "Not exist" ; } // Driver code $arr = array( 10, 4, 8, 13, 5 ); $n = sizeof($arr) / sizeof($arr[0]); findPair($arr, $n); // This code is contributed by nitin mittal. ?> |
Output :
8 5
An Efficient solution is to store all element in an hash table (unordered_set in C++) and check one by one all pairs and check its sum exists in set or not. If it exists in set then print pair. If no pair found in array then print not exists .
C++
// C++ program to find pair whose sum already // exists in array #include <bits/stdc++.h> using namespace std; // Function to find pair whose sum exists in arr[] void findPair(int arr[], int n) { // Hash to store all element of array unordered_set<int> s; for (int i = 0; i < n; i++) s.insert(arr[i]); bool found = false; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check sum already exists or not if (s.find(arr[i] + arr[j]) != s.end()) { cout << arr[i] << " " << arr[j] << endl; found = true; } } } if (found == false) cout << "Not exist" << endl; } // Driven code int main() { int arr[] = { 10, 4, 8, 13, 5 }; int n = sizeof(arr) / sizeof(arr[0]); findPair(arr, n); return 0; } |
Java
// Java program to find pair whose sum // already exists in array import java.util.*; import java.lang.*; import java.io.*; class Getpairs { // Function to find pair whose sum // exists in arr[] public static void findPair(int[] arr, int n) { /* store all the array elements as a Hash value*/ HashSet<Integer> s = new HashSet<Integer>(); for (Integer i : arr) { s.add(i); } /* Run two loop and check for the sum in the Hashset*/ /* if not a single pair exist then found will be false else true*/ boolean found = false; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int sum = arr[i] + arr[j]; if (s.contains(sum)) { /* if the sum is present in hashset then found become true*/ found = true; System.out.println(arr[i] + " " + arr[j]); } } } if (found == false) System.out.println("Not Exist "); } // driver function public static void main(String args[]) { int[] arr = { 10, 4, 8, 13, 5 }; int n = arr.length; findPair(arr, n); } } // This code is contributed by Smarak Chopdar |
Python3
# Python3 program to find pair whose # sum already exist in arrar # Function to find pair whose # sum sxists in arr[] def findPair(arr, n): # hash to store all element of array s = {i : 1 for i in arr} found = False for i in range(n): for j in range(i + 1, n): # check if sum already exists or not if arr[i] + arr[j] in s.keys(): print(arr[i], arr[j]) found = True if found == False: print("Not exist") # Driver code arr = [10, 4, 8, 13, 5] n = len(arr) findPair(arr, n) # This code is contributed # by Mohit Kumar |
C#
// C# program to find pair whose sum // already exists in array using System; using System.Collections.Generic; class Getpairs { // Function to find pair whose sum // exists in arr[] public static void findPair(int[] arr, int n) { /* store all the array elements as a Hash value*/ HashSet<int> s = new HashSet<int>(); foreach (int i in arr) { s.Add(i); } /* Run two loop and check for the sum in the Hashset*/ /* if not a single pair exist then found will be false else true*/ bool found = false; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int sum = arr[i] + arr[j]; if (s.Contains(sum)) { /* if the sum is present in hashset then found become true*/ found = true; Console.WriteLine(arr[i] + " " + arr[j]); } } } if (found == false) Console.WriteLine("Not Exist "); } // Driver code public static void Main() { int[] arr = { 10, 4, 8, 13, 5 }; int n = arr.Length; findPair(arr, n); } } // This code contributed by Rajput-Ji |
Output:
8 5
Time Complexity : O(n2)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments