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

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Problem :

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++

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.

 
public static void findPairsEqualsToXUsingHashing(int arr[], int X) {
    HashMap elementIndexMap = new HashMap();
    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:

package org.arpit.java2blog;

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 elementIndexMap = new HashMap();
        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 above program, you will get 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