techInterview Discussion

Let A be an array of random integers. User gives N which can be any integer and the program has to return a pair of numbers from array whose sum equals N.

e.g A = {3,6,1,9,6,5};

Let N = 10 then your program should return 1,9. In case of many pairs, return first pair. Try to make this as fast as possible, please specify the complexities also.

Try with/without extra space, just to give direction to discussion, otherwise I have seen people sticking to one perticular approach even when better thing can be done.

Okay, I'm trying to think my way around this question and can't think of anything apart from a naive answer unless there are some constraints on the random numbers in the array.

It seems that you'll have to iterate through A, keeping a store of the numbers that you need to find to return a pair. i.e. for the example A you'd need to find values of 7,4,9,1,4,5. The trick must be in storing these numbers in such a way so as to quickly test the next value in A against all the numbers you're looking for.

One way of doing this would be to have each new number that you're looking for index an array of the prime numbers. So the first value in A is 3, this leaves a remainder of 7, the seventh prime number is 17 (primes running from 2 upwards). You multiply some stored variable P by this value (P starting with a value of 1). You then try to divide P by the prime indexed by the next value in A. If it divides leaving 0, then you've found the other value you require. If it doesn't then you multiply P by the prime indexed by the value that A[i] is looking for (i.e. 10 - A[i]). This way P continues to store the information of every number being searched for and one modulus each iteration will check every one of them. You can also check for duplicates in A, by checking that P%(N - A[i]) does not equal zero before adding it.

However this will only work if all values in A are less than N or you're allowed negative indexes (or you check for the largest value in A and use the remainder of that from N as an offset). It would also fall apart if the value of P eventually became larger than the maximum value of a long.

Given the inellegence of this answer I'm guessing it's not "the one" but as no-one else was forthcoming I thought I'd at least start a discussion :)

First sort the array
Then for each number i in the array, we need to find N-i.  Do a binary search on N-i

time is n*log(n)

Hmmmmm from the statement "In case of many pairs, return first pair." I'm guessing we're not allowed to sort the array.

Not that your answer isn't simple and elegant if we are :)

I think we need clarification about what constitutes the "first pair".  Suppose our list is {4,3,2,1} and N is 5.  Is {4,1} the "first pair", or is {3,2} the "first pair"?  (One of them starts earlier, the other one ends earlier, and both have the same "average index" so to speak...)

Once we know what the rule is, then Howard's solution will work.  We just have to make sure we store the original index for each value when we build a sorted list for binary searches.  Each time we find a valid pair, we can "score" it by looking at the indices and determining how "early" the pair is in the original list.  Keep track of the earliest one we've found.  Since Howard's solution iterates through all pairs, then once we are finished we should have the earliest pair.

If we want to cut down on the "extra storage" used, then something like MikeD's solution looks attractive, since it doesn't require O(N) extra space, it just requires "one number" to keep track of the other numbers we're looking for.

But the problem is it blows up too quickly.  Consider if our list is simply the numbers from 1 to 11... we'll end up multiplying the first 11 prime numbers together, and get 200,560,490,130.

Along those same lines, let us consider "bit vectors".  Basically, we just need N "bits", so if N is more than the machine word size then we'll end up needing more than just one extra integer; a typical implementation is an array of N/(word size in bits) integers.  So we still need extra storage, but the amount needed is based on the size of N rather than the size of the list.

With this approach, we just set a bit when we see a number, and check if the bit for its "partner" is already set.  This algorithm is O(n) time where n is the size of the list, so performance is better than the binary-search approach.

Again, how we define the "first pair" matters.  As described, this approach will yield the pair that "ends first".  If we want the one that "begins first", we must start our search at the end of the list... and when we find one, don't just return immediately, but keep searching.  The pair we want to return will be the last one we find.

If N is very large and the list is not very long, then the binary-search approach is better.  Also, if you can have negative numbers in the list, then you have to use the binary-search approach because you cannot simply ignore values that are greater than N in that case.

Well, if you've got a lot of space and want to do things in approximately O(n) you can insert the entire array into a hash table (O(n)) and then loop through through the array.  Each test for the existence of the number you'll need is O(1), so this ends up being O(n) worst case.

Ahh, here we go.  This doesn't require any extra space but it will be destructive.  We're working with positive numbers only, right?  If not this requires a trivial modification.

1)  Sort the array (n log n).
2)  Discard everything above N.  (log n)
3)  Partition the array about N/2. (log n)
4)  You now need to pick one number out of each subarray. 
5)  Iterate through the smaller sub-array, testing it against the larger.  Time complexity is better than m*n log ((1-m) * n), where n is the portion of the array that is in the smaller subarray.  m's upper bound is 1/2.

But wait, why split it into 2 arrays when we could split it into four?  Call the arrays A,B,C, and D.  The pair has to be in A/B or C/D.  Now our time complexity is, at worse, 2mn * log((1-m)n), but m's upper bound is now 1/4. 

I believe, don't quote me on this, that every time you split the arrays you get faster.

What about the following approaches.


1. Merge sort:

Using merge sort we can do this on O(n*logn).
While doing merging, just check whether the sum = X, if it it then return true else continue.

2. Bit vector:

I like this one. Have a bit vector of size equal to total number of ints.
 
1.clear all bits
2.for each element a[i] in the array
  - if bit sum-a[i] is set, return sum-a[i], a[i]
  - else, set bit a[i]

This will need constant storage and time complexity is O(n) in any case.

How about below approach:
1) Sort the array O(nlogn)- Inplace-Quicksort
2) take two indexs namely start- points to 0th element, end-ponts to last element.
3)while(start!=end){
 if(sum == a[start] + a[end]){
        /* done */
}else if (sum > a[start] + a[end])
          start++;
else
    end++;
}

I am not sure about the answer, but you may find something at this website:
www.technical-interview.com

Sorry guys I meant:
www.technicalinterview.info

One shot approach without array sorting:

for (i = 0; i < cnt - 1; i++) {
    for (j = i + 1; j < cnt; j++) {
        if (sum == ary[i] + ary[j]) {
            //found, print if you want...
        }
    }
}