Quick Programming Puzzle
rzwitserloot posted in programming on December 7th, 2006
Using whatever language you like, try this problem.
Including reading the assignment, this took me less than 20 minutes, hence the ‘quick’ in the title of this post 
.
It’s written in java, generic to a certain extent, and takes (on my macbook CoreDuo 1.8Ghz with a load of apps open) 2.7 milliseconds to reach an answer (calculated by running 10,000 times and taking an average). Not the best of metrics but should be enough to impress that this test is really far too small to make a reasonable timing measurement.
No cheating by peeking at the comments!
December 7th, 2006 at 21:31
interesting. my brute force C-style Java solution takes 0.0069 ms using the example data (as there is a zero sum solution early on), otherwise up to 500ms.
What’s your code?
December 8th, 2006 at 2:58
Should show up at the linked site any day. Expanding to the ‘9′ to ‘20′ reveals a calculation time of about 30 seconds.
I was wondering which of the two implementation strategies was gonna work better. Clearly the recursive one wins this battle.
Here’s my code: Steve3.java.
Memoizes very aggressively. Some -mx512m is advised if you bump the ‘9′ to a ‘20′ to make it more interesting.
December 8th, 2006 at 9:42
This problem is a special case of the subset sum problem described here:
http://en.wikipedia.org/wiki/Subset_sum_problem
Using dynamic programming it can be solved in time and space O(n*k) where n is the number of elements in the array and k is the span of the values (max-min).
In this case the span is 230, and with 31 elements the running time is O(7130) which should complete in a very short amount of time on modern computers.
Note that the length of the array is not the main problem here since it is not likely to be very big due to memory constraints, but rather using bigger numbers will quickly increase the running time (which is why this problem is NP-complete).