Question 19 : Find all pairs of elements from an array whose sum is equal to given number

Given an array, we need to find all pairs whose sum is equal to the number X.

For example:

array[]={ -40, -5, 1, 3, 6, 7, 8, 20 };
Pair of elements whose sum is equal to 15 :  7, 8 and -5, 20

Solution :

Solution 1:

You can check each and every pair of numbers and find the sum equals to  X.
Java code:

public static void findPairsWithSumEqualsToXBruteForce(int arr[], int X) {
    if (arr.length < 2)
        return;
 
    System.out.println("The pair whose sum is equal to 15 using brute force method: ");
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            int tempSum = arr[i] + arr[j];
 
            if (tempSum == X) {
                System.out.println(arr[i] + " " + arr[j]);
            }
        }

    }
}

Solution 2

• Sort the array
• We will maintain two indexes one at beginning (l=0) and one at end (r=n-1)
• iterate until l <  r
• Check if arr[l] + arr[r] is equal to X
• if Yes, then print the pair and do l++, r–
• If arr[l] + arr[r] is less than X, this means if we want to find sum close to X, do r–
• If arr[l] + arr[r] is greater than X,this means if we want to find sum close to X , do l++

Java code:

public static void findPairsEqualsToX(int arr[], int X) {
 
    int n = arr.length;
    if (n < 2)
        return;
    Arrays.sort(arr);
    System.out.println("The pair whose sum is equal to 15 : ");
    // left and right index variables
    int l = 0, r = n - 1;
 
    while (l < r) {
        int currentSum = arr[l] + arr[r];
        if (currentSum == X) {
            System.out.println(arr[l] + " " + arr[r]);
            l++;
            r--;
        } else if (arr[l] + arr[r] < X)
            l++;
        else
            r--;
    }
}

Time complexity : O(NLogN)

Solution 3:

Using Hashing

• Put array element in HashMap with element as key and its index as value.
• Iterate over array arr[]
• Check for arr[i],  if X-arr[i] is present in HashMap.
• If yes, we have found the pair and print it.

Java code:

public static void findPairsEqualsToXUsingHashing(int arr[], int X) {
    HashMap<Integer, Integer> elementIndexMap = new HashMap<Integer, Integer>();
    System.out.println("The pair whose sum is equal to 15 : ");
    for (int i = 0; i < arr.length; i++) {
        elementIndexMap.put(arr[i], i);
    }
    for (int i = 0; i < arr.length; i++) {
        // we have used elementIndexMap.get(X-arr[i])!=i to avoid using same
        // element twice
        if (elementIndexMap.get(X - arr[i]) != null && elementIndexMap.get(X - arr[i]) != i) //
        {
            System.out.println(arr[i] + " " + (X - arr[i]));
        }
    }
}

Time complexity : O(NLogN) Space complexity : O(N)

Java program to find all pairs whose sum is equal to given number::

import java.util.Arrays;
import java.util.HashMap;
 
public class FindPairEqualToGivenNumberMain {
 
    public static void main(String[] args) {
        int array[] = { -40, -5, 1, 3, 6, 7, 8, 20 };
        findPairsWithSumEqualsToXBruteForce(array, 15);
        findPairsEqualsToX(array, 15);
        findPairsEqualsToXUsingHashing(array, 15);
    }
 
    public static void findPairsWithSumEqualsToXBruteForce(int arr[], int X) {
        if (arr.length < 2)
            return;
 
        System.out.println("The pair whose sum is closest to 15 using brute force method: ");
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int tempSum = arr[i] + arr[j];
 
                if (tempSum == X) {
                    System.out.println(arr[i] + " " + arr[j]);
                }
            }
        }
    }
 
    public static void findPairsEqualsToX(int arr[], int X) {
 
        int n = arr.length;
        if (n < 2)
            return;
        Arrays.sort(arr);
        System.out.println("The pair whose sum is closest to 15 : ");
        // left and right index variables
        int l = 0, r = n - 1;
 
        while (l < r) {
            int currentSum = arr[l] + arr[r];
            if (currentSum == X) {
                System.out.println(arr[l] + " " + arr[r]);
                l++;
                r--;
            } else if (arr[l] + arr[r] < X)
                l++;
            else
                r--;
        }
    }
 
    public static void findPairsEqualsToXUsingHashing(int arr[], int X) {
        HashMap<Integer, Integer> elementIndexMap = new HashMap<Integer, Integer>();
        System.out.println("The pair whose sum is closest to 15 : ");
        for (int i = 0; i < arr.length; i++) {
            elementIndexMap.put(arr[i], i);
        }
        for (int i = 0; i < arr.length; i++) {
            // we have used elementIndexMap.get(X-arr[i])!=i to avoid using same
            // element twice
            if (elementIndexMap.get(X - arr[i]) != null && elementIndexMap.get(X - arr[i]) != i) //
            {
                System.out.println(arr[i] + " " + (X - arr[i]));
            }
        }
    }
}
 

When you run the above program, you will get the below output:

The pair whose sum is closest to 15 using brute force method: 
-5 20
7 8

The pair whose sum is closest to 15 : 
-5 20
7 8

The pair whose sum is closest to 15 : 
-5 20
7 8
8 7
20 -5

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

   

Share This

• Facebook
• Twitter
• Linkedin
• Pinterest