10 April 2008

Sums of sets

Two more programming puzzles.

You want to partition sqrt(1), sqrt(2), ..., sqrt(n) into two sets that minimize the difference of the sums. What's the best complexity you can get?

And one via David Eppstein. (Don't look unless you want a big hint.) "Let S be a set (or multiset) of positive integers. Describe an efficient algorithm for finding the smallest positive integer x such that x is not the sum of some subset of S."

No comments:

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.