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 :

Given a  array,we need to find all pairs whose sum is equal to 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:

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

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012