CODEWITHSUNDEEP
calgorithmoptimization
suraj_fale
suraj_fale

Reputation: 960

Find a target value in an unsorted array of integers by performing additions of integers

Following is an interview question asked by 'Amazon' to me. I still haven't come up with a optimized solution.

Problem Statement:
Given an unsorted array of integers n. Return 'true' if the addition of any integers from that array matches with the target value else return 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.

Test 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.
So I am looking for any method or algorithm which will optimized this problem more.

Thank you in advance!

Upvotes: 4

Views: 3009

Answers (3)

Benjamin Gruenbaum
Benjamin Gruenbaum

Reputation: 276306

NOTE This answer is still informative so I'm keeping it, but after OP's edit it is less relevant.

Here is how I would solve it in O(n) runtime complexity and O(n) space complexity using a concept called 'Hashing'. (Where n is the size of the array)

Let's call the number I'd like to get d

First I would create some sort of HashTable (a key value store). HashMaps have O(1) insert, get and contains. You can read about them here

Then I would put every object in the cell d-object in the hash map. Before I check the next number x I'd check if the hash map contains a value at cell x. If it does we've 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 d-x to map if it is not already in map
    return false

Upvotes: 1

nneonneo
nneonneo

Reputation: 179452

The subset-sum problem is a well-known NP-complete problem. Here, I'm going to assume that you are looking for any set of numbers to sum to the target (if you're actually looking for only two numbers, there's a five-line solution using a counting hashtable which runs in O(n) time).

There are two basic approaches. The first is just to test every possible subsequence. As you've already observed, that takes O(2n) time (exponential), which is intractable if n is 1000.

The second is to keep track of what sums are obtainable from prefixes of the list. This is a very simple approach, and works well if the integers are bounded. By way of example, if the input is n k-bit integers, it has computational complexity O(2kn2) (pseudopolynomial): the biggest the sums can get is 2kn, so the table has at most 2kn2 entries. This is a typical dynamic programming approach, where the subproblem is 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 implementing 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're curious, here's a solution to the pair-sum problem. It runs in O(n) time and tells you if the array has two numbers summing to the target.

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 t-k 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

Upvotes: 9

hamilton.lima
hamilton.lima

Reputation: 1920

What about sort the array, and for each element calculate the pair necessary to the target value and search for it ? that would make the cost of sorting + plus each binary search.

Upvotes: 0

Related Questions