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

Last updated on March 14th, 2017 at 11:09 am

Previous
Next

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:

Solution :

Solution 1:

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

 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:

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:

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

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

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

Previous
Next

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.

Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog