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!

@NiteeshMehra, consecutive in the sense that *every* number between minimum and maximum exists (possibly exactly once). — phimuemue, Mar 11 '12 at 16:46
@NiteeshMehra `1, 5, 2, 4, 3` would contain consecutive numbers only, while `1, 5, 6, 4, 3` would not contain just consecutive numbers only (`2` is missing). — phimuemue, Mar 11 '12 at 16:49
You have to be careful about the hashtable solution. Suppose the target is 8 and the array contains a single 4. You don't want to report 4 + 4 as a solution. (Or do you?) Also, if we're only talking theoretically, then assuming that the values are bounded (by, say, 2^32), then you can use radix sort to sort in O(n) time. — Ted Hopp, Mar 11 '12 at 16:50
By saying consecutive here, I mean do they need to follow each other in the given sequence???....In your examples..[6,4] and [9,1] were in a sequence.....4 was neighbor of 6 and 1 was neighbor of 9.... — Shashank Kadne, Mar 11 '12 at 16:52
@TedHopp if only one 4 exists in the array , then no. If 2 or more , then yeah. — h4ck3d, Mar 11 '12 at 16:53
@TedHopp: The problem you describe can be easily solved if you create the hashset and check if an element exist in the same iteration. [and not first creating a full hash-set, and only later checking for a pair] — amit, Mar 11 '12 at 16:56
@amit - Yes, that's an example of how to "be careful" (as I had put it). — Ted Hopp, Mar 11 '12 at 16:59
Taken from CLRS 3rd Edition: 2.3-7 * Describe a **Θ(nlgn)** time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x. So maybe it can not be done in O(n) time using O(1) space. — Avi Cohen, Mar 11 '12 at 17:40
Can anyone please explain the correctness of the first method "an O(nlogn) solution - sort + check sum with 2 iterators (beginning and end)". I mean, yes, it is giving the correct output but I am not getting it intuitively. Why is this method working correctly ? — Vikas Mangal, Mar 28 '15 at 10:34

score 19 · Answer 1 · edited May 23 '17 at 12:17

19

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".

edited May 23 '17 at 12:17

Community

1
1

answered Mar 11 '12 at 17:43

Evgeny Kluev

24,287
7
55
98

1

I have trouble saying that radix sort actually takes time O(N), since it depends on the size of the machine word. For a fixed machine it's O(N), but more generally this is O(N log U), where U is the maximum possible integer representable. – templatetypedef Mar 11 '12 at 20:04
1

@EvgenyKluev : Seems quite close to what is required. But then radix sort is O(kn) which is not any better than O(nlogn). Could you explain how you are calling it O(n) ? – h4ck3d Mar 11 '12 at 22:11
@EvgenyKluev : If each key is of 9 digits then complexity of radix would be high – h4ck3d Mar 11 '12 at 22:29
1

@templatetypedef, @NiteeshMehra, yes, in general case radix sort is O(N log U). Also, computing the hash function is O(log U). Filling and using the hashtable is O(N log U). Since OP's second solution assumes complexity O(N), we have O(N log U) = O(N). Or O(U) = 1. Which allows me to assume O(N) for radix sort. Isn't it reasonable? Anyway, if O(U) > 1, we cannot have O(N) solution at all because we have to process `N log U` bits (worst case) or `N log N` bits (on average, for uniformly distributed numbers and N < U). – Evgeny Kluev Mar 12 '12 at 04:33
@NiteeshMehra, If each key is of 9 decimal digits, it contains about 32 bits. You can sort it in 16 passes (as explained in my answer), or you can do it in 8 passes with 8 bits per pass and 256 counters. In practice, it may be better than O(N log N) of comparison sort - if N is large, or it may be worse if N is small. – Evgeny Kluev Mar 12 '12 at 04:42

score 7 · Answer 2 · edited Aug 30 '13 at 06:26

7

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

edited Aug 30 '13 at 06:26

SergV

1,269
8
20

answered Feb 18 '13 at 15:54

Changqi Cai

89
1
5

1

Your second solution is not correct. How can we do binary search in unsorted array? – Hengameh May 05 '15 at 10:56
5

also the forth one! it is not correct! your array is not sorted, you cannot increment or decrement indexes. you may miss some of them. – Hengameh May 05 '15 at 10:58
@Hengameh: The second solution is correct if we sort the array first. Notice that using a proper sorting algorithm, the runtime will still be O(N*logN) – Ari Sep 29 '16 at 17:27
@Hengameh: The 4th solution would also be correct, if we sort the array first. Obviously, in that case, the run time will not be O(N) anymore, but it will be O(N*LogN). – Ari Sep 29 '16 at 17:34
Why is 4 more optimal than 3? O(N) is better! 4 only makes sense if you are space constrained. – Joseph Garvin Mar 19 '17 at 00:04
Misleading answer – Infinite Mar 12 '22 at 02:49

score 3 · Answer 3 · answered Dec 01 '12 at 04:49

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.

answered Dec 01 '12 at 04:49

Sandeep

47
1

Whats the difference between hashing and your solution ? – h4ck3d Dec 01 '12 at 09:29
Nothing his is still O(N) space – Sep 23 '13 at 21:31
4

OP explicitly said no extra space.. why is this answer upvoted? – seeker Nov 16 '13 at 00:57
try it with array=[ 1, 2, 10, 3, 4], and sum = 20 – chouaib May 29 '15 at 04:48

score 2 · Answer 4 · answered May 29 '15 at 16:10

    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]);
        }
    }

}

Howl Blindfolds · Answer 5 · 2018-01-25T21:32:41.843

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]

It would be great if you add a few lines to explain how your code answers the question. — Yannis, Jan 25 '18 at 13:19
Found a bug in the code. When the the key and the value is 5. Added a slicing to search in parts. — Howl Blindfolds, Jan 25 '18 at 21:29

PengOne · Answer 6 · 2012-03-11T17:17:14.120

1

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.

edited Mar 11 '12 at 17:17

answered Mar 11 '12 at 16:57

PengOne

48,188
17
130
149

1

Shouldn't `Pj` be more like `P[j]`? – svick Mar 11 '12 at 17:26
With these assumptions, can't we just create an array which will be histogram/set of size M? – amit Mar 11 '12 at 17:32
3

if `M` is constant, I have a simpler algorithm. Make `M/2` passes on the array, looking for 1 and `M-1` on the 1st pass, 2 and `M-2` on the 2nd pass and so on, in O(NM) = O(N) time. – Ali Ferhat Mar 11 '12 at 17:33
4

Saying that `M` is O(1) seems like cheating. If `M` is O(1) then there will be only `O(1)` unique values in the array that can participate in the sum, so you'd just need O(n) time to find those values and then any algorithm you use will be O(1) time and space. – interjay Mar 11 '12 at 17:39

Suraj · Answer 7 · 2013-08-30T05:56:06.657

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;
}

score 0 · Answer 8 · answered Nov 14 '13 at 18:48

`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)
*******/
}

score 0 · Answer 9 · edited Feb 03 '14 at 03:14

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;
}

score 0 · Answer 10 · edited Mar 10 '14 at 07:56

0

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)

edited Mar 10 '14 at 07:56

Hardik

3,815
3
35
45

answered Mar 10 '14 at 07:34

Piyush Shandilya

75
8

Sorting makes it O(nlogn). The question asks for O(n). – Gokul Mar 09 '19 at 09:38

igor · Answer 11 · 2014-05-30T17:33:48.543

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

score 0 · Answer 12 · answered May 22 '15 at 22:34

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;
                }
            }
        }
    }

score 0 · Answer 13 · answered Dec 07 '15 at 03:54

0

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

answered Dec 07 '15 at 03:54

Erict2k

15
4

1

I can see the notational ease. Care to argue space and time complexity? The questions about ends with `O(n) time and O(1) space?` – greybeard Dec 07 '15 at 07:39

score 0 · Answer 14 · edited Apr 01 '16 at 08:45

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.

score 0 · Answer 15 · answered Nov 10 '16 at 15:38

0

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!

answered Nov 10 '16 at 15:38

alkurmtl

141
1
7

score 0 · Answer 16 · answered Jun 21 '17 at 07:38

// 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);
}

}

score 0 · Answer 17 · answered Mar 11 '12 at 16:48

0

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.

answered Mar 11 '12 at 16:48

Blender

289,723
53
439
496

sorting is `O(nlogn)`, iterating over consecutive pairs fails, for example: `{9,3,1}` sum is 10. – amit Mar 11 '12 at 16:49
1

@Blender iterating over pairs = O(n^2) – h4ck3d Mar 11 '12 at 16:50
1

@amit: sorting *could* be O(n) depending on the constraints on the input numbers – BrokenGlass Mar 11 '12 at 16:50
I'm not sure if there exists a `O(n)` solution that takes up `O(1)` space for something this complicated. – Blender Mar 11 '12 at 16:51
@NiteeshMehra: For a sorted list, it's `O(n)`. You're just counting from `0 -> len(list)`. – Blender Mar 11 '12 at 16:51
@BrokenGlass Best known integer sorting algorithm is `O(n*sqrt(loglogn))`, for unbounded range [AFAIK] - and it is not `O(1)` space. The OP didn't give any constraint about a bounded range, so I don't think we can assume there is – amit Mar 11 '12 at 16:53
2

@amit what is best sorting algorithm with `O(n*sqrt(loglogn))` for unbounded range? – Saeed Amiri Mar 11 '12 at 18:19
@SaeedAmiri: http://dl.acm.org/citation.cfm?id=652131 They claim to have `O(n*sqrt(loglogn))` *expected time* for integer sorting, which can be improved to `O(n*sqrt(loglogU))` for integers bounded to `[0,U]` – amit Mar 11 '12 at 19:18
@amit, what you referenced is [Integer sorting](http://en.wikipedia.org/wiki/Integer_sorting#Algorithms_for_small_keys) not general sorting algorithm, also is 0(n\sqrt {\log \log K}) where `K` is biggest number in inputs, In fact it's kind of bounded range. current `O` wrote in acm portal is wrong (in abstract), currently I don't have access to full paper, But If they wrote `O(n\sqrt {\log \log n})` in their full paper, they should be fabulous billioner, because they solved one of a biggest problems of TCS. I'm sure this is wrong in general and is some kind of bounded result. – Saeed Amiri Mar 11 '12 at 20:12
@SaeedAmiri, you can read the article using [this link](http://www.scribd.com/doc/62574071/Integer-Sorting-in-O-n-sqrt-log-log-n-Expected-Time-and-Linear-Space). It looks interesting. Actually, authors say it is only a theory paper and it does not have any immediate practical use because of too large constants hidden in O-notation. – Evgeny Kluev Mar 11 '12 at 20:55

score -2 · Answer 18 · answered Apr 14 '17 at 08:31

    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();
    }

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

18 Answers18

Python 2.7 Implementation:

Output:

Linked

Related