Find 2 numbers in an unsorted array equal to a given sum

Question

We need to find pair of numbers in an array whose sum is equal to a given value.

A = {6,4,5,7,9,1,2}

Sum = 10 Then the pairs are - {6,4} , {9,1}

I have two solutions for this .

• an O(nlogn) solution - sort + check sum with 2 iterators (beginning and end).
• an O(n) solution - hashing the array. Then checking if sum-hash[i] exists in the hash table or not.

But , the problem is that although the second solution is O(n) time , but uses O(n) space as well.

So , I was wondering if we could do it in O(n) time and O(1) space. And this is NOT homework!

Answer 1

Use in-place radix sort and OP's first solution with 2 iterators, coming towards each other.

If numbers in the array are not some sort of multi-precision numbers and are, for example, 32-bit integers, you can sort them in 2*32 passes using practically no additional space (1 bit per pass). Or 2*8 passes and 16 integer counters (4 bits per pass).

---

Details for the 2 iterators solution:

First iterator initially points to first element of the sorted array and advances forward. Second iterator initially points to last element of the array and advances backward.

If sum of elements, referenced by iterators, is less than the required value, advance first iterator. If it is greater than the required value, advance second iterator. If it is equal to the required value, success.

Only one pass is needed, so time complexity is O(n). Space complexity is O(1). If radix sort is used, complexities of the whole algorithm are the same.

---

If you are interested in related problems (with sum of more than 2 numbers), see "Sum-subset with a fixed subset size" and "Finding three elements in an array whose sum is closest to an given number".

Answer 2

This is a classic interview question from Microsoft research Asia.
How to Find 2 numbers in an unsorted array equal to a given sum.

[1]brute force solution
This algorithm is very simple. The time complexity is O(N^2)

[2]Using binary search
Using bianry searching to find the Sum-arr[i] with every arr[i], The time complexity can be reduced to O(N*logN)

[3]Using Hash
Base on [2] algorithm and use hash, the time complexity can be reduced to O(N), but this solution will add the O(N) space of hash.

[4]Optimal algorithm:

Pseduo-code:

for(i=0;j=n-1;i<j)
   if(arr[i]+arr[j]==sum) return (i,j);
else if(arr[i]+arr[j]<sum) i++;
else j--;
return(-1,-1);

or

If a[M] + a[m] > I then M--
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.

And, Is this quesiton completely solved? No. If the number is N. This problem will become very complex.

The quesiton then:
How can I find all the combination cases with a given number?

This is a classic NP-Complete problem which is called subset-sum.
To understand NP/NPC/NP-Hard you'd better to read some professional books.

References:
[1]http://www.quora.com/Mathematics/How-can-I-find-all-the-combination-cases-with-a-given-number
[2]http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 3

for (int i=0; i < array.size(); i++){
  int value = array[i];
  int diff = sum - value; 
  if (! hashSet.contains(diffvalue)){
      hashSet.put(value,value);
  } else{
       printf(sum = diffvalue + hashSet.get(diffvalue));
  } 
}

--------
Sum being sum of 2 numbers.

Answer 4

    public void printPairsOfNumbers(int[] a, int sum){
    //O(n2)
    for (int i = 0; i < a.length; i++) {
        for (int j = i+1; j < a.length; j++) {
            if(sum - a[i] == a[j]){
                //match..
                System.out.println(a[i]+","+a[j]);
            }
        }
    }

    //O(n) time and O(n) space
    Set<Integer> cache = new HashSet<Integer>();
    cache.add(a[0]);
    for (int i = 1; i < a.length; i++) {
        if(cache.contains(sum - a[i])){
            //match//
            System.out.println(a[i]+","+(sum-a[i]));
        }else{
            cache.add(a[i]);
        }
    }

}

Answer 5

If you assume that the value M to which the pairs are suppose to sum is constant and that the entries in the array are positive, then you can do this in one pass (O(n) time) using M/2 pointers (O(1) space) as follows. The pointers are labeled P1,P2,...,Pk where k=floor(M/2). Then do something like this

for (int i=0; i<N; ++i) {
  int j = array[i];
  if (j < M/2) {
    if (Pj == 0)
      Pj = -(i+1);   // found smaller unpaired
    else if (Pj > 0)
      print(Pj-1,i); // found a pair
      Pj = 0;
  } else
    if (Pj == 0)
      Pj = (i+1);    // found larger unpaired
    else if (Pj < 0)
      print(Pj-1,i); // found a pair
      Pj = 0;
  }
}

You can handle repeated entries (e.g. two 6's) by storing the indices as digits in base N, for example. For M/2, you can add the conditional

  if (j == M/2) {
    if (Pj == 0)
      Pj = i+1;      // found unpaired middle
    else
      print(Pj-1,i); // found a pair
      Pj = 0;
  } 

But now you have the problem of putting the pairs together.

Answer 6

Create a dictionary with pairs Key (number from the list) and the Value is the number which is necessary to obtain a desired value. Next, check the presence of the pairs of numbers in the list.

def check_sum_in_list(p_list, p_check_sum):
    l_dict = {i: (p_check_sum - i) for i in p_list}
    for key, value in l_dict.items():
        if key in p_list and value in p_list:
            return True
    return False


if __name__ == '__main__':
    l1 = [1, 3, 7, 12, 72, 2, 8]
    l2 = [1, 2, 2, 4, 7, 4, 13, 32]

    print(check_sum_in_list(l1, 10))
    print(check_sum_in_list(l2, 99))

Output:
True
Flase

version 2

import random


def check_sum_in_list(p_list, p_searched_sum):
    print(list(p_list))
    l_dict = {i: p_searched_sum - i for i in set(p_list)}
    for key, value in l_dict.items():
        if key in p_list and value in p_list:
            if p_list.index(key) != p_list.index(value):
                print(key, value)
                return True
    return False


if __name__ == '__main__':
    l1 = []
    for i in range(1, 2000000):
        l1.append(random.randrange(1, 1000))

    j = 0
    i = 9
    while i < len(l1):
        if check_sum_in_list(l1[j:i], 100):
            print('Found')
            break
        else:
            print('Continue searching')
            j = i
            i = i + 10

Output:
...
[154, 596, 758, 924, 797, 379, 731, 278, 992, 167]
Continue searching
[808, 730, 216, 15, 261, 149, 65, 386, 670, 770]
Continue searching
[961, 632, 39, 888, 61, 18, 166, 167, 474, 108]
39 61
Finded
[Finished in 3.9s]

Answer 7

Does the obvious solution not work (iterating over every consecutive pair) or are the two numbers in any order?

In that case, you could sort the list of numbers and use random sampling to partition the sorted list until you have a sublist that is small enough to be iterated over.

Answer 8

public static ArrayList<Integer> find(int[] A , int target){
    HashSet<Integer> set = new HashSet<Integer>();
    ArrayList<Integer> list = new ArrayList<Integer>();
    int diffrence = 0;
    for(Integer i : A){
        set.add(i);
    }
    for(int i = 0; i <A.length; i++){
        diffrence = target- A[i];
    if(set.contains(diffrence)&&A[i]!=diffrence){
        list.add(A[i]);
        list.add(diffrence);
        return list;
    }
     }
    return null;
}

Answer 9

`package algorithmsDesignAnalysis;

 public class USELESStemp {
 public static void main(String[] args){
    int A[] = {6, 8, 7, 5, 3, 11, 10}; 

    int sum = 12;
    int[] B = new int[A.length];
    int Max =A.length; 

    for(int i=0; i<A.length; i++){
        B[i] = sum - A[i];
        if(B[i] > Max)
            Max = B[i];
        if(A[i] > Max)
            Max = A[i];

        System.out.print(" " + B[i] + "");

    } // O(n) here; 

    System.out.println("\n Max = " + Max);

    int[] Array = new int[Max+1];
    for(int i=0; i<B.length; i++){
        Array[B[i]] = B[i];
    } // O(n) here;

    for(int i=0; i<A.length; i++){  
    if (Array[A[i]] >= 0)
        System.out.println("We got one: " + A[i] +" and " + (sum-A[i]));
    } // O(n) here;

} // end main();

/******
Running time: 3*O(n)
*******/
}

Answer 10

Below code takes the array and the number N as the target sum. First the array is sorted, then a new array containing the remaining elements are taken and then scanned not by binary search but simple scanning of the remainder and the array simultaneously.

public static int solution(int[] a, int N) {

    quickSort(a, 0, a.length-1);    // nlog(n)

    int[] remainders = new int[a.length];

    for (int i=0; i<a.length; i++) {
        remainders[a.length-1-i] = N - a[i];     // n
    }

    int previous = 0;

    for (int j=0; j<a.length; j++) {            // ~~ n

        int k = previous;

        while(k < remainders.length && remainders[k] < a[j]) {
            k++;
        }

        if(k < remainders.length && remainders[k] == a[j]) {
            return 1;
        }

        previous = k;
    }

    return 0;
}

Answer 11

Shouldn't iterating from both ends just solve the problem?

Sort the array. And start comparing from both ends.

if((arr[start] + arr[end]) < sum) start++;
if((arr[start] + arr[end]) > sum) end--;
if((arr[start] + arr[end]) = sum) {print arr[start] "," arr[end] ; start++}
if(start > end)  break;

Time Complexity O(nlogn)

Answer 12

if its a sorted array and we need only pair of numbers and not all the pairs we can do it like this:

public void sums(int a[] , int x){ // A = 1,2,3,9,11,20 x=11
    int i=0 , j=a.length-1;
    while(i < j){
      if(a[i] + a[j] == x) system.out.println("the numbers : "a[x] + " " + a[y]);
      else if(a[i] + a[j] < x) i++;
      else j--;
    }
}

1 2 3 9 11 20 || i=0 , j=5 sum=21 x=11
1 2 3 9 11 20 || i=0 , j=4 sum=13 x=11
1 2 3 9 11 20 || i=0 , j=4 sum=11 x=11
END

Answer 13

The following code returns true if two integers in an array match a compared integer.

 function compareArraySums(array, compare){

        var candidates = [];

        function compareAdditions(element, index, array){
            if(element <= y){
                candidates.push(element);
            }
        }

        array.forEach(compareAdditions);

        for(var i = 0; i < candidates.length; i++){
            for(var j = 0; j < candidates.length; j++){
                if (i + j === y){
                    return true;
                }
            }
        }
    }

Answer 14

Python 2.7 Implementation:

import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
    if n[0] + n[1] == targetsum:
    print str(n[0]) + " + " + str(n[1])

Output:

1 + 4
2 + 3

Answer 15

https://github.com/clockzhong/findSumPairNumber

#! /usr/bin/env python
import sys
import os
import re


#get the number list
numberListStr=raw_input("Please input your number list (seperated by spaces)...\n")
numberList=[int(i) for i in numberListStr.split()]
print 'you have input the following number list:'
print numberList

#get the sum target value
sumTargetStr=raw_input("Please input your target number:\n")
sumTarget=int(sumTargetStr)
print 'your target is: '
print sumTarget


def generatePairsWith2IndexLists(list1, list2):
    result=[]
    for item1 in list1:
        for item2 in list2:
            #result.append([item1, item2])
            result.append([item1+1, item2+1])
    #print result
    return result

def generatePairsWithOneIndexLists(list1):
    result=[]
    index = 0
    while index< (len(list1)-1):
        index2=index+1
        while index2 < len(list1):
            #result.append([list1[index],list1[index2]])
            result.append([list1[index]+1,list1[index2]+1])
            index2+=1
        index+=1
    return result


def getPairs(numList, target):
    pairList=[]
    candidateSlots=[] ##we have (target-1) slots 

    #init the candidateSlots list
    index=0
    while index < target+1:
        candidateSlots.append(None)
        index+=1

    #generate the candidateSlots, contribute O(n) complexity
    index=0
    while index<len(numList):
        if numList[index]<=target and numList[index]>=0:
            #print 'index:',index
            #print 'numList[index]:',numList[index]     
            #print 'len(candidateSlots):',len(candidateSlots)
            if candidateSlots[numList[index]]==None:
                candidateSlots[numList[index]]=[index]
            else:
                candidateSlots[numList[index]].append(index)
        index+=1

    #print candidateSlots

    #generate the pairs list based on the candidateSlots[] we just created
    #contribute O(target) complexity
    index=0
    while index<=(target/2):
        if candidateSlots[index]!=None and candidateSlots[target-index]!=None:
            if index!=(target-index):
                newPairList=generatePairsWith2IndexLists(candidateSlots[index], candidateSlots[target-index])
            else:
                newPairList=generatePairsWithOneIndexLists(candidateSlots[index])
            pairList+=newPairList
        index+=1

    return pairList

print getPairs(numberList, sumTarget)

I've successfully implemented one solution with Python under O(n+m) time and space cost. The "m" means the target value which those two numbers' sum need equal to. I believe this is the lowest cost could get. Erict2k used itertools.combinations, it'll also cost similar or higher time&space cost comparing my algorithm.

Answer 16

If numbers aren't very big, you can use fast fourier transform to multiply two polynomials and then in O(1) check if coefficient before x^(needed sum) sum is more than zero. O(n log n) total!

Answer 17

// Java implementation using Hashing import java.io.*;

class PairSum { private static final int MAX = 100000; // Max size of Hashmap

static void printpairs(int arr[],int sum)
{
    // Declares and initializes the whole array as false
    boolean[] binmap = new boolean[MAX];

    for (int i=0; i<arr.length; ++i)
    {
        int temp = sum-arr[i];

        // checking for condition
        if (temp>=0 && binmap[temp])
        {
            System.out.println("Pair with given sum " +
                                sum + " is (" + arr[i] +
                                ", "+temp+")");
        }
        binmap[arr[i]] = true;
    }
}

// Main to test the above function
public static void main (String[] args)
{
    int A[] = {1, 4, 45, 6, 10, 8};
    int n = 16;
    printpairs(A,  n);
}

}

Answer 18

    public static void Main(string[] args)
    {
        int[] myArray =  {1,2,3,4,5,6,1,4,2,2,7 };
        int Sum = 9;

            for (int j = 1; j < myArray.Length; j++)
            {                    
                if (myArray[j-1]+myArray[j]==Sum)
                {
                    Console.WriteLine("{0}, {1}",myArray[j-1],myArray[j]);
                }
            }            
        Console.ReadLine();
    }