Find the target value in an unsorted array of integers by adding integers

Question

The following is the interview question asked me by Amazon. I still haven't come up with an optimized solution.

Problem:
Given an unsorted array of integers n. Returns 'true' if adding any integers from this array matches the target else value returns false .

Note:

1)'n' could be 1000 or 10,000. 2) Target value could be 'negative' 3) It may be addition of any 'k' integers (not only two) , where k<=n. 

Verification Condition:

  i/p:- Array A[]= {6,7,3,0,12,-5,-6,100} Target = 8 o/p:- TRUE As, 6+7+(-5)=8 

If we try to do it linearly or normally, it will take O (2 ^ n) time complexity .
Therefore, I am looking for any method or algorithm that will optimize this problem more.

Thank you in advance!

Answer 1

The problem of a subset of sums is a well-known NP-complete problem. Here I am going to suggest that you are looking for any set of numbers to sum with a goal (if you are really looking for only two numbers, there is a five-line solution using a hash counting table that works in O (n)).

There are two main approaches. The first is just to check every possible subsequence. As you already noticed, this takes O (2 ⁿ ) time (exponential), which is unsolvable if n is 1000.

Secondly, to track what amounts can be obtained from the list prefixes. This is a very simple approach and works well if integers are limited. As an example, if the input is n k-bit integers, it has computational complexity O (2 ^k n ² ) (pseudo-polynomial): the largest sums can get 2 ^k n, so the table has no more than 2 ^k n ² entries. This is a typical approach to dynamic programming, where the subtask T[s][k] = (A[1..k] has a subsequence summing to s) , and the final solution is given by T[target][n] .

Here's a solution in Python that implements this:

 def subset_sum(A, target): T = {0} # T[s][0] = (TRUE iff s == 0) for i in A: T |= {x + i for x in T} return target in T 

Examples:

 >>> subset_sum([-5,6,7,1,0,12,5,-6,100], 13) True >>> subset_sum([95, -120, 22, 14491], 13) False 

---

Bonus: if you are interested, here is a solution to the problem of a couple of sums. It starts in O (n) time and tells you if the array has two numbers summed for the purpose.

 from collections import Counter def pair_sum(A, t): C = Counter(A) for k,v in C.iteritems(): if t == k+k and v > 1: return True # k is in the array twice elif t != k+k and tk in C: return True return False 

Examples:

 >>> pair_sum([3,3,3,4], 13) False >>> pair_sum([3,3,3,10], 13) True >>> pair_sum([7,7,2], 14) True >>> pair_sum([7,14,2], 14) False 

Answer 2

NOTE This answer is still informative, so I save it, but after editing the OP it is less relevant.

Here's how I could solve this in O(n) complexity and O(n) complexity using a concept called Hashing. (Where n is the size of the array)

Call the number I would like to receive d

First, I would create a kind of HashTable (storage of key values). HashMaps has O(1) insert, get, and contains. You can read about them here.

Then I would put each object in the d-object of the cell in the hash map. Before checking the next x number, I would check if the hash map contains the value in cell x. If so, we found our match.

Here is some pseudo code (I think this is better for a general answer than C code)

 CheckIfTwoNumbersComplementTo(d,arr) map <-- new HashTable for each number x in Arr if(map contains a key for x) return true else add dx to map if it is not already in map return false 

Answer 3

How about sorting the array, and for each element, calculate the pair needed for the target value and do a search? what would make the sorting cost + plus each binary search.