How to write an objective C code to check if the sum of any three numbers in an array/list matches a given number?

Question

Possible Duplicate:
Finding three elements in an array whose sum is closest to an given number

How can I write an Objective C code to check if the sum of any three numbers in an array/list matches a given number?

What have you tried? Are you thinking that the brute-force enumeration of combinations of three elements is a bad idea? — Ray Toal, Jan 18 '13 at 06:54
I see you have editted your post to make it clear you want an Objective-C solution. Notwithstanding, you might want to read the answer provided by `songlj` as he provides an algorithm in words. All you need to do is code it up. It's almost the best way to learn. Doing it yourself! THe link above by Henrik is also great! — DaMainBoss, Jan 18 '13 at 18:34

songlj · Accepted Answer · 2013-01-18T07:44:01.117

3

step 1: sort, O(nlgn)

step 2: iterate every number, say A,(this costs O(n)), then check whether the sum of any two numbers equals to the given number minus A(this is a classic problem which costs O(n))

total complexity: O(n^2)

edited Jan 18 '13 at 07:44

answered Jan 18 '13 at 06:54

songlj

927
1
6
10

Are you sure about complexity .? Because iterating for two numbers itself take O(n^2) time and then searching for element Given number - sum of iterating numbers takes O(log(n)) so it shoul be O(n^2(log(n))) – Imposter Jan 18 '13 at 09:01
@Imposter surely. please consider or search for this problem: check whether the sum of any two numbers equals to a given number – songlj Jan 18 '13 at 09:17
Yes i agree that " check whether the sum of any two numbers equals to a given number " takes O(nlog(n)) time but now for searching third element it takes some time right ? what is the additionally incured time ? In question you mentioned given number(say P) is constant but here P- A is varying for every pair of number we pick . Am i going wrong somewhere ?Help me – Imposter Jan 18 '13 at 09:44

score 1 · Answer 2 · answered Jan 18 '13 at 10:30

Here is another way

X,Y,Z are indices of array and P is given Number .

If conditions is X+Y=P then we sort the array and then We pick each element and then search P-Y in remaining array .If searching is successful then fine are else return False .

So searching takes log(n) time(binary search) so for n elements it takes O(nlog(n)) time .

Now Our condition is X+Y+Z=P We deduce it to X+Y=P-Z

Now Pick a number Z and calculate P-Z and let it be R . 
Now the problem is deduce to X+Y=R .So time complexity is O(nlog(n))
Since R varies n times for n picks in array so complexity is O((N^2)log(n))) .

score 0 · Answer 3 · answered Jan 18 '13 at 07:41

Here's a brute-force solution in Python, valuable only for its succinctness, not at all for its efficiency:

import itertools
def anyThreeEqualTo(list, value):
    return any([sum(c) == value for c in itertools.combinations(list, 3)])

Another idea:

import itertools
def anyThreeEqualTo(list, value):
    for c in itertools.combinations(list, 3)])
        if sum(c) == value:
            return True
    return False

These solutions try each of the triplets in turn until one is found with the desired sum.

How to write an objective C code to check if the sum of any three numbers in an array/list matches a given number?

3 Answers3