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

I was asked this same question during an interview, and this is the scheme I had in mind. There's an improvement left to do, to permit negative numbers, but it would only be necessary to modify the indexes. Space-wise ain't good, but I believe running time here would be O(N)+O(N)+O(subset of N) -> O(N). I may be wrong.

void find_sum(int *array_numbers, int x){
 int i, freq, n_numbers; 
 int array_freq[x+1]= {0}; // x + 1 as there could be 0’s as well
 if(array_numbers)
 {
  n_numbers = (int) sizeof(array_numbers);
  for(i=0; i<n_numbers;i++){ array_freq[array_numbers[i]]++; } //O(N) 
  for(i=0; i<n_numbers;i++) 
  { //O(N) 
   if ((array_freq[x-array_numbers[i]] > 0)&&(array_freq[array_numbers[i]] > 0)&&(array_numbers[i]!=(x/2)))
   { 
    freq = array_freq[x-array_numbers[i]] * array_freq[array_numbers[i]];
    printf(“-{%d,%d} %d times\n”,array_numbers[i],x-array_numbers[i],freq ); 
    // “-{3, 7} 6 times” if there’s 3 ‘7’s and 2 ‘3’s
    array_freq[array_numbers[i]]=0;
    array_freq[x-array_numbers[i]]=0; // doing this we don’t get them repeated
   }
  } // end loop
  if ((x%2)=0)
  {
   freq = array_freq[x/2];
   n_numbers=0;
   for(i=1; i<freq;i++)
   { //O([size-k subset])
    n_numbers+= (freq-i); 
   } 
   printf(“-{%d,%d} %d times\n”,x/2,x/2,n_numbers);
  }
  return;
 }else{
 return; // Incoming NULL array 
 printf(“nothing to do here, bad pointer\n”);
 }
}

Critics are welcomed.

Answer 2

In java, this is depends on max number in array. it returns an int[] having the indexes of two elements. it is O(N).

  public static int[] twoSum(final int[] nums, int target) {
    int[] r = new int[2];
    r[0] = -1;
    r[1] = -1;
    int[] vIndex = new int[0Xffff];
    for (int i = 0; i < nums.length; i++) {
        int delta = 0Xfff;
        int gapIndex = target - nums[i] + delta;
        if (vIndex[gapIndex] != 0) {
            r[0] = vIndex[gapIndex];
            r[1] = i + 1;
            return r;
        } else {
            vIndex[nums[i] + delta] = i + 1;
        }
    }
    return r;
}

Answer 3

My solution in Java (Time Complexity O(n)), this will output all the pairs with a given sum

import java.util.HashMap;
import java.util.Map;

public class Test {
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Map<Integer, Integer> hash = new HashMap<>();
    int arr[] = {1,4,2,6,3,8,2,9};
    int sum = 5;
    for (int i = 0; i < arr.length; i++) {
        hash.put(arr[i],i);
    }

    for (int i = 0; i < arr.length; i++) {
        if(hash.containsKey(sum-arr[i])){
            System.out.println(i+ " " +  hash.get(sum-arr[i]));
        }
    }
}
}

Answer 4

Here is a solution witch takes into account duplicate entries. It is written in javascript and runs using sorted and unsorted arrays. The solution runs in O(n) time.

var count_pairs_unsorted = function(_arr,x) {
  // setup variables
  var asc_arr = [];
  var len = _arr.length;
  if(!x) x = 0;
  var pairs = 0;
  var i = -1;
  var k = len-1;
  if(len<2) return pairs;
  // tally all the like numbers into buckets
  while(i<k) {
    asc_arr[_arr[i]]=-(~(asc_arr[_arr[i]]));
    asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
    i++;
    k--;
  }
  // odd amount of elements
  if(i==k) {
    asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
    k--;
  }
  // count all the pairs reducing tallies as you go
  while(i<len||k>-1){
    var y;
    if(i<len){
      y = x-_arr[i];
      if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[i]])>1) {
        if(_arr[i]==y) {
          var comb = 1;
          while(--asc_arr[_arr[i]] > 0) {pairs+=(comb++);}
        } else pairs+=asc_arr[_arr[i]]*asc_arr[y];
        asc_arr[y] = 0;
        asc_arr[_arr[i]] = 0;
      }

    }
    if(k>-1) {
      y = x-_arr[k];
      if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[k]])>1) {
        if(_arr[k]==y) {
          var comb = 1;
          while(--asc_arr[_arr[k]] > 0) {pairs+=(comb++);}
        } else pairs+=asc_arr[_arr[k]]*asc_arr[y];
        asc_arr[y] = 0;
        asc_arr[_arr[k]] = 0;
      }

    }
    i++;
    k--;
  }
  return pairs;
}

Start at both side of the array and slowly work your way inwards keeping a count of how many times each number is found. Once you reach the midpoint all numbers are tallied and you can now progress both pointers counting the pairs as you go.

It only counts pairs but can be reworked to

• find the pairs
• find pairs < x
• find pairs > x

Enjoy!

Answer 5

If you have a sorted array you can find such a pair in O(n) by moving two pointers toward the middle

i = 0
j = n-1
while(i < j){
   if      (a[i] + a[j] == target) return (i, j);
   else if (a[i] + a[j] <  target) i += 1;
   else if (a[i] + a[j] >  target) j -= 1;
}
return NOT_FOUND;

The sorting can be made O(N) if you have a bound on the size of the numbers (or if the the array is already sorted in the first place). Even then, a log n factor is really small and I don't want to bother to shave it off.

proof:

If there is a solution (i*, j*), suppose, without loss of generality, that i reaches i* before j reaches j*. Since for all j' between j* and j we know that a[j'] > a[j*] we can extrapolate that a[i] + a[j'] > a[i*] + a[j*] = target and, therefore, that all the following steps of the algorithm will cause j to decrease until it reaches j* (or an equal value) without giving i a chance to advance forward and "miss" the solution.

The interpretation in the other direction is similar.

Answer 6

An O(N) time and O(1) space solution that works on a sorted array:

Let M be the value you're after. Use two pointers, X and Y. Start X=0 at the beginning and Y=N-1 at the end. Compute the sum sum = array[X] + array[Y]. If sum > M, then decrement Y, otherwise increment X. If the pointers cross, then no solution exists.

You can sort in place to get this for a general array, but I'm not certain there is an O(N) time and O(1) space solution in general.