8

I've been breaking a sweat over this question I've been asked to answer (it's technically homework). I've considered a hashtable but I'm kind of stuck on the exact specifics of how I'd make this work

Here's the question:

Given k sets of integers A1,A2,..,Ak of total size O(n), you should determine whether exist a1 ϵ A1, a2 ϵ A2,..,ak ϵ Ak, such that a1+a2+..+ak−1 =ak. Your algorithm should run in Tk(n) time, where Tk(n) = O(nk/2 × log n) for even k, and O(n(k+1)/2) for odd values of k.

Can anyone give me a general direction so that I can come closer to solving this?

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
Arnon
  • 2,237
  • 15
  • 23
  • 4
    congratulations on admitting homework. Do you have *any* answer to the problem (disregarding complexity)? If so, what do you analyze it's complexity as? Do you think your approach is completely wrong-headed, or are there specific parts that you think are faulty? – Damien_The_Unbeliever Dec 17 '11 at 15:50
  • The only thing I could figure out that would work 100% was the most naive implementation of n^n (ie. checking ALL the options). Obviously this is not the right way to go :( – Arnon Dec 17 '11 at 15:53
  • 1
    I wonder if this would be better suited to Math Overflow? – Jonathan Grynspan Dec 17 '11 at 16:10

1 Answers1

9

Divide the k sets into two groups. For even k, both groups have k/2 sets each. For odd k, one group has (k+1)/2 and the other has (k-1)/2 sets. Compute all possible sums (taking one element from each set) within each group. For even k, you will get two arrays, each with nk/2 elements. For odd k, one array has n(k+1)/2 and the other array has n(k-1)/2 elements. The problem is reduced to the standard one "Given two arrays, check if a specified sum can be reached by taking one element from each array".

viswanathgs
  • 776
  • 1
  • 4
  • 5
  • Thanks for your answer! This seems right intuitively, but I can't completely figure out how this actually reduced the problem. Can you elaborate a tiny bit? – Arnon Dec 17 '11 at 16:29
  • Given two arrays of size O(n) each, you can find if a sum exists in O(n*log n). The solution is not too difficult. I would feel guilty if I give it out to you since you have mentioned it is a homework! – viswanathgs Dec 17 '11 at 16:52
  • @viswanathgs: you can even solve the two arrays problem in O(n) time on average. – Massimo Cafaro Dec 19 '11 at 14:57
  • @unforgiven: That is only if the arrays are sorted, right? Or is there something I'm not looking at? – viswanathgs Dec 19 '11 at 17:43