Table of Contents
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:
|
1 2 3 4 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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])); } } } |
Java program to find all pairs whose sum is equal to given number:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
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])); } } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
