How do you find all pairs of elements in an array
whose sum is equal to a given number?
Problem :
Given an array of
integers, you have to find all pairs of elements in this array such that
whose sum must be equal to a given number.For example, if {4, 5, 7, 11, 9, 13, 8, 12} is an array and 20 is the given number, then you have to find all pairs of elements in this array whose sum must be 20. In this example, (9, 11), (7, 13)and (8, 12) are such pairs whose sum is 20.
Logic Used To Find All
Pairs Of Elements In An Array Whose Sum Is Equal To A Given Number :
We use brute-force method
to solve this problem. We take one element at a time and search for other
element such that they add up to a given number. For this, we use two for loops
to iterate through the elements. We print such pairs of elements whose sum
is equal to a given number. This method works for both positive and negative
numbers and also for unsorted array.
Java Program To Find
All Pairs Of Elements In An Array Whose Sum Is Equal To A Given Number :
public class PairsOfElementsInArray { static void findThePairs(int inputArray[], int inputNumber) { System.out.println("Pairs of elements whose sum is " + inputNumber + " are : "); for (int i = 0; i < inputArray.length; i++) { for (int j = i + 1; j < inputArray.length; j++) { if (inputArray[i] + inputArray[j] == inputNumber) { System.out.println(inputArray[i] + " + " + inputArray[j] + " = " + inputNumber); } } } } public static void main(String[] args) { findThePairs(new int[] { 4, 6, 5, -10, 8, 5, 20 }, 10); findThePairs(new int[] { 4, -5, 9, 11, 25, 13, 12, 8 }, 20); findThePairs(new int[] { 12, 13, 40, 15, 8, 10, -15 }, 25); findThePairs(new int[] { 12, 23, 125, 41, -75, 38, 27, 11 }, 50); } }
Output :
Pairs of elements
whose sum is 10 are :4 + 6 = 10
5 + 5 = 10
-10 + 20 = 10
Pairs of elements whose sum is 20 are :
-5 + 25 = 20
9 + 11 = 20
12 + 8 = 20
Pairs of elements whose sum is 25 are :
12 + 13 = 25
40 + -15 = 25
15 + 10 = 25
Pairs of elements whose sum is 50 are :
12 + 38 = 50
23 + 27 = 50
125 + -75 = 50
Note : Time Complexity of this solution is O(n^2). So, this is not the recommended solution for large arrays. There is better method exist which gives time complexity of O(nLogn). But, it works only for sorted arrays. Below is another solution to find all pairs of elements in an array whose sum is equal to a given number.
Alternative Method :
public class PairsOfElementsInArray { static void findThePairs(int inputArray[], int inputNumber) { // Sorting the given array Arrays.sort(inputArray); System.out.println("Pairs of elements whose sum is " + inputNumber + " are : "); // Initializing i to first index int i = 0; // Initializing j to last index int j = inputArray.length - 1; // Till i crosses j, perform the following task while (i < j) { // If inputArray[i]+inputArray[j] is equal to inputNumber if (inputArray[i] + inputArray[j] == inputNumber) { // then Print inputArray[i] and inputArray[j] System.out.println(inputArray[i] + " + " + inputArray[j] + " = " + inputNumber); // Increment i i++; // Decrement j j--; } // If inputArray[i]+inputArray[j] is smaller than inputNumber else if (inputArray[i] + inputArray[j] < inputNumber) { // then increment i i++; } // If inputArray[i]+inputArray[j] is greater than inputNumber else if (inputArray[i] + inputArray[j] > inputNumber) { // then decrement j j--; } } } public static void main(String[] args) { findThePairs(new int[] { 4, 6, 5, -10, 8, 5, 20 }, 10); findThePairs(new int[] { 4, -5, 9, 11, 25, 13, 12, 8 }, 20); findThePairs(new int[] { 12, 13, 10, 15, 8, 40, -15 }, 25); findThePairs(new int[] { 12, 23, 10, 41, 15, 38, 27 }, 50); } }
Output :
Pairs of elements
whose sum is 10 are :-10 + 20 = 10
4 + 6 = 10
5 + 5 = 10
Pairs of elements whose sum is 20 are :
-5 + 25 = 20
8 + 12 = 20
9 + 11 = 20
Pairs of elements whose sum is 25 are :
-15 + 40 = 25
10 + 15 = 25
12 + 13 = 25
Pairs of elements whose sum is 50 are :
12 + 38 = 50
23 + 27 = 50
EmoticonEmoticon