find pair of numbers in array that add to given su

Question

Question: Given an unsorted array of positive integers, is it possible to find a pair of integers from that array that sum up to a given sum?

Constraints: This should be done in O(n) and in-place (without any external storage like arrays, hash-maps) (you can use extra variables/pointers)

If this is not possible, can there be a proof given for the same?

Answer 1

Here is a solution in python:

a = [9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 2, 8, 9, 2, 2, 8,
     9, 2, 15, 11, 21, 8, 9, 12, 2, 8, 9, 2, 15, 11, 21, 7, 9, 2, 23, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 12, 9, 2, 15, 11, 21, 8, 9, 2, 2,
     8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 7.12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9,
     2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 0.87, 78]
i = 0
j = len(a) - 1
my_sum = 8
finded_numbers = ()
iterations = 0
while(OK):
    iterations += 1
    if (i < j):
        i += 1
    if (i == j):
        if (i == 0):
            OK = False
            break
        i = 0
        j -= 1
    if (a[i] + a[j] == my_sum):
        finded_numbers = (a[i], a[j]) 
        OK = False
print finded_numbers
print iterations

Answer 2

1. Use count sort to sort the array O(n).

2. take two pointers one starts from 0th index of array, and another from end of array say (n-1).

   run the loop until low <= high

   Sum = arr[low] + arr[high]  
   if(sum == target)
          print low, high
   if(sum < target)
          low++
   if(sum > target)
          high--
   

   Step 2 to 10 takes O(n) time, and counting sort takes O(n). So total time complexity will be O(n).

Answer 3

AS @PengOne mentioned it's not possible in general scheme of things. But if you make some restrictions on i/p data.

1. all elements are all + or all -, if not then would need to know range (high, low) and made changes.
2. K, sum of two integers is sparse compared to elements in general.
3. It's okay to destroy i/p array A[N].

Step 1: Move all elements less than SUM to the beginning of array, say in N Passes we have divided array into [0,K] & [K, N-1] such that [0,K] contains elements <= SUM.

Step 2: Since we know bounds (0 to SUM) we can use radix sort.

Step 3: Use binary search on A[K], one good thing is that if we need to find complementary element we need only look half of array A[K]. so in A[k] we iterate over A[ 0 to K/2 + 1] we need to do binary search in A[i to K].

So total appx. time is, N + K + K/2 lg (K) where K is number of elements btw 0 to Sum in i/p A[N]

Note: if you use @PengOne's approach you can do step3 in K. So total time would be N+2K which is definitely O(N)

We do not use any additional memory but destroy the i/p array which is also not bad since it didn't had any ordering to begin with.

Answer 4

First off, sort the array using radix sort. That'll set you back O(kN). Then proceed as @PengOne suggest.

Answer 5

Here's an O(N) algorithm. It relies on an in-place O(N) duplicate removal algorithm, and the existence of a good hash function for the ints in your array.

First, remove all duplicates from the array.

Second, go through the array, and replace each number x with min(x, S-x) where S is the sum you want to reach.

Third, find if there's any duplicates in the array: if 'x' is duplicated, then 'x' and 'S-x' must have occurred in the original array, and you've found your pair.

Answer 6

In javascript : This code when n is greater then the time and number of iterations increase. Number of test done by the program will be equal to ((n*(n/2)+n/2) where n is the number of elements.The given sum number is discarded in if (arr[i] + arr[j] === 0) where 0 could be any number given.

var arr = [-4, -3, 3, 4];          
                var lengtharr = arr.length;        
                var i = 0;                         
                var j = 1;                         
                var k = 1;                          
                do {                                                    
                    do {
                        if (arr[i] + arr[j] === 0) { document.write(' Elements arr [' + i + '] [' + j + '] sum 0'); } else { document.write('____'); }
                     j++;
                    } while (j < lengtharr);        
                    k++;
                    j = k;
                    i++;
                } while (i < (lengtharr-1));