How do you find all pairs of elements in an array whose sum is equal to a given number?

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

NextGen4IT

How do you find all pairs of elements in an array whose sum is equal to a given number?

Problem :

Logic Used To Find All Pairs Of Elements In An Array Whose Sum Is Equal To A Given Number :

Java Program To Find All Pairs Of Elements In An Array Whose Sum Is Equal To A Given Number :

Share this