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

Question

We need to find a pair of numbers in the array, the sum of which is equal to the 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.

• O (nlogn) solution is to sort + check the sum using two iterators (start and end).
• O (n) solution is hashing the array. Then check if sum-hash[i] exists in the hash table or not.

But the problem is that although the second solution is O (n) time, it also uses O (n) space.

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

Answer 1

Use in-place radial sorting and the first OP solution with two iterators approaching each other.

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

---

Details for a solution with two iterators:

First, the iterator first points to the first element of the sorted array and advances. The second iterator initially points to the last element of the array and moves backward.

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

Only one pass is required, so the time complexity is O (n). The complexity of the space is O (1). If radix sorting is used, the complexity of the whole algorithm is the same.

---

If you are interested in related problems (with a sum of more than two numbers), see "Sum of a subset with a fixed size of a subset" and "Search for three elements in an array whose sum is closest to a 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 amount.

[1] brute force decision
This algorithm is very simple. Time complexity O (N ^ 2)

[2] Using binary search
Using a bianri search to find Sum-arr [i] with each arr [i], the time complexity can be reduced to O (N * logN)

[3] Use of the hash
Based on the algorithm [2] and using a hash, the time complexity can be reduced to O (N), but this solution will add O (N) hash space.

[4] The 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 it a quesiton? No. If the number is N. This problem will be very complicated.

Then quesiton:
How can I find all combinations of cases with a given number?

This is a classic NP-complete problem called a subset.
To understand NP / NPC / NP-Hard, you better read a few professional books.

Literature:
[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

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

 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 duplicate entries (for example, two 6), for example, storing indices as numbers in the base N For M/2 you can add 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 a problem with pairing.

Answer 5

  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 6

Does the obvious solution work (iteration over each consecutive pair) or two numbers in any order?

In this case, you can sort the list of numbers and use random sampling to split the sorted list until you have a sublist that is small enough to be repeated.

Answer 7

 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 8

 `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 9

Below, the code takes an array and the number N as the target amount. First, the array is sorted, then a new array containing the remaining elements is taken and then scanned not by binary search, but by simply scanning the remainder and the array at the same time.

 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 10

Should iteration from both ends solve the problem?

Sort an 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; 

O(nlogn) Time Complexity O(nlogn)

Answer 11

if its array is sorted , and we need only a pair of numbers, and not all pairs, we can do this as follows:

 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 12

The following code returns true if two integers in the array match the 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 13

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

Exit:

 1 + 4 2 + 3 

Answer 14

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 have successfully implemented one solution with Python under O (n + m) time and space. "M" means the target value equal to the sum of these two numbers. I think this is the lowest cost. Erict2k used itertools.combinations, it will also cost similar or higher time and volume costs comparing my algorithm.

Answer 15

If the numbers are not very large, you can use the fast Fourier transform to multiply the two polynomials, and then in O (1) check whether the coefficient up to the sum x ^ (the required sum) is greater than zero. O (n log n) total!

Answer 16

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

class PairSum {private static final int MAX = 100000; // Maximum size of the 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 17

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