Let’s write
a program to find pair in array whose sum is equal to given number. We can achieve
this by using two methods: by sorting & without sorting.
Find a pair in array whose sum is equal to given number by using Sorting
Steps:
1.
First sort the array.
2.
Initialize left and right indexes as l = 0, r =
arr.length – 1
3.
Loop the array until l < r
4.
Verify arr[l] + arr[r] is less than sum, then
increase l
5.
Verify arr[l] + arr[r] is greater than sum, then
decrease r.
6.
If arr[l] + arr[r] is equal to sum then return
true, if not return false.
Example explanation:
·
Given array is : {5, 4, 2, 8}, sum is 9.
·
Sort the array: { 2, 4, 5, 8}
·
Initialize l = 0 and r = 3
·
arr[0] + arr[3] à
2+8 > 9 , then decrement “r”. Now r = 2
·
arr[0] + arr[2] à
2+5 < 9 , then increment “l”. Now l = 1
·
arr[1] + arr[2] à
4+5 == 9, then return true.
import java.util.Arrays;
import java.util.HashSet;
import
java.util.Scanner;
public class
PairInArray {
public static void
main(String[] args) {
Scanner sc = new
Scanner(System.in);
int[] arr = {5,
4, 2, 8};
System.out.print("Enter sum: ");
int sum = sc.nextInt();
System.out.println("is
pair found : " +isPairFindInArray(arr, sum) );
}
public static boolean
isPairFindInArray(int[] arr, int sum) {
boolean isFound = false;
int l=0, r=arr.length-1;
Arrays.sort(arr); //
Sorting array elements
while(l < r) {
if( (arr[l] + arr[r]) < sum )
l++;
else if( (arr[l] + arr[r]) > sum )
r--;
else {
isFound = true;
break;
}
}
return isFound;
}
}
Output:
Output:
Enter sum: 9
is pair found : true
Find a pair in array whose sum is equal to given number without Sorting
Steps:
1.
Loop the array elements.
2.
Subtract the array element from sum and store in
the set.
3.
Verify is set contains array element or not?
4.
If yes, return true else return false.
Example Explanation:
·
Given array is : {5, 4, 2, 8}, sum is 9.
·
Set doesn’t contain arr[0]
·
Sum – arr[0] à
9-5 = 4, store in the set.
·
Set contains arr[1], return true
import java.util.Arrays;
import
java.util.HashSet;
import
java.util.Scanner;
public class
PairInArray {
public static void
main(String[] args) {
Scanner sc = new
Scanner(System.in);
int[] arr = {5,
4, 2, 8};
System.out.print("Enter
sum: ");
int sum = sc.nextInt();
System.out.println("is
pair found : " +isPairFindInArray(arr, sum) );
}
public static boolean
isPairFindInArray(int[] arr, int sum) {
boolean isFound = false;
HashSet set = new HashSet();
for(int i=0; i<arr.length; i++) {
if( set.contains(arr[i]) ) {
isFound = true;
break;
}else {
set.add( sum - arr[i] );
}
}
return isFound;
}
}
Output:
Enter sum: 9
is pair found : true