2

I recently came across an interesting Java Algorithm statement

Given an array int[] arr{} and a number x, find if there are any 2 numbers in the array whose sum is equal to x.

Hint: Solve it in 3 ways with the following complexities O(n^2), O(n log n) and O(n)

O(n^2) approach is a simple brute force logic. O(n log n) possibly involves merge sorting and using a binary search - though I am able to exactly figure out how to fit in binary search here. I am totally clueless about O(n) algorithm.

Simple Brute force logic:

for(i = 0; i < arr.length; i++){
    for(j=0; j<arr.length; j++){
       if(arr[i] + arr[j] == x){
         return x;
       }
    }
}

Any pointers?

Suvasis
  • 1,451
  • 4
  • 24
  • 42
Prasanna
  • 2,593
  • 7
  • 39
  • 53
  • Where is your try? What's wrong with that? – Ruchira Gayan Ranaweera Sep 25 '14 at 11:31
  • 1
    Duplicate? http://stackoverflow.com/questions/9656789/find-2-numbers-in-an-unsorted-array-equal-to-a-given-sum?rq=1 and http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number?rq=1 – Thilo Sep 25 '14 at 11:33

3 Answers3

1

Here is a HashSet based solution with n time and space complexity.

 private static boolean twoNumbersInArraySumIsEqualToX(int[] input, int x) {
    //create HashSet and store each element as key from array
    Set<Integer> set =  new HashSet<Integer>();
    for (int elem_ : input) set.add(elem_);

    //Iterate through the array and find if (x - elem) exists in set
    for (int elem_ : input) {
      if(set.contains(x - elem_)) return true;
    }
    return false;
  }
SJha
  • 1,510
  • 1
  • 10
  • 17
0

I think the O(n) intended solution is a HashMap. Adding and testing n values is O(n) or close.

PS: Despite the fact that I was downvoted, I stand by my answer.

OK, maybe I should have explained the algorithm: for each a[i], check if (x-a[i]) is in the HashMap. If yes, you are done. If not, add a[i] to the HashMap and continue.

Florian F
  • 1,300
  • 1
  • 12
  • 28
0

If we assume that the array is already sorted, you can do the following:

int i =0;
int j = arr.length-1;
while (i<j){
    if (arr[i]+arr[j]>x){
        j--;
        continue;
    }
    else if (arr[i]+arr[j]<x){
        i++;
        continue;
    }
    else { // arr[i]+arr[j]==x
        return true;
    }
}
return false;
Hikari
  • 1