Given a list of numbers and a number k, return whether any two numbers from the list add up to k

Question

This question was asked in the Google programming interview. I thought of two approaches for the same:

1. Find all the subsequences of length. While doing so compute the sum and of the two elements and check if it is equal to k. If ye, print Yes, else keep searching. This is a brute Force approach.

2. Sort the array in non-decreasing order. Then start traversing the array from its right end. Say we have the sorted array, {3,5,7,10} and we want the sum to be 17. We will start from element 10, index=3, let's denote the index with 'j'. Then include the current element and compute required_sum= sum - current_element. After that, we can perform a binary or ternary search in array[0- (j-1)] to find if there is an element whose value is equal to the required_sum. If we find such an element, we can break as we have found a subsequence of length 2 whose sum is the given sum. If we don't find any such element, then decrease the index of j and repeat the above-mentioned steps for resulting subarray of length= length-1 i.e. by excluding the element at index 3 in this case.

Here we have considered that array could have negative as well as positive integers.

Can you suggest a better solution than this? A DP solution maybe? A solution that can further reduce it's time complexity.

Answer 1

This question can be easily solved with the help of set in O(N) time and space complexity.First add all the elements of array into set and then traverse each element of array and check whether K-ar[i] is present in set or not.

Here is the code in java with O(N) complexity :

boolean flag=false;
HashSet<Long> hashSet = new HashSet<>();
for(int i=0;i<n;i++){
    if(hashSet.contains(k-ar[i]))flag=true;
    hashSet.add(ar[i]);
}
if(flag)out.println("YES PRESENT");
else out.println("NOT PRESENT");