import java.util.*;
class Main {
public static void main(String[] args) {
// given an array find the pair that equals to given sum
// {1,2,3,5,6} --> sum = 4
// {1,2,5, 9} --> sum = 4
// Given sorted array, and only integers and can have negative numbers
// if there is a matching pair return true, otherwise return false, return true if you find atleat one matching pair
// main goal is find the efficient solution
// Naive, brute force method
int [] inputArray = {1,2,5,9,25,34,87};
System.out.println(new Main().evaluateMatchingPairUsingTreeSet(inputArray, 33));
}
public boolean evaluateMatchingPairBruteForce(int[] input, int sum){
for(int i = 0 ; i < input.length; i++){
for(int j = i+1; j < input.length; j++){
int calSum = input[i] + input[j];
if(calSum == sum){
return true;
}
}
}
return false;
}
// optimised code
// I would consider the below approach where i add the first and last sum and if is more than the sum i will decrease the index or increase the index if greater than
public boolean evaluateMatchingPair(int[] input, int sum){
int higherIndex = input.length-1;
int lowerIndex = 0;
while(lowerIndex<higherIndex){
int calSum = input[higherIndex] + input[lowerIndex];
if(calSum == sum)
return true;
else if(calSum < sum)
lowerIndex++;
else
higherIndex--;
}
return false;
}
// the above solution only works for sorted numbers what if the numbers are not sorted how would you find
// {1,3,2,5,6} --> sum = 4
public boolean evaluateMatchingPairUsingTreeSet(int[] input, int sum){
Set<Integer> comp = new TreeSet<>();
for(int i =0; i<input.length; i++){
if(comp.contains(input[i]))
return true;
comp.add(sum-input[i]);
}
return false;
}
}
