Algo problem (Ashish) : array sum

Q: Given a pair of integers (SUM,COUNT), construct every ascending array of COUNT poker cards with sum == SUM. You only have 9 cards, numbered 1 to 9. Clearly COUNT can’t go beyond 9. (In other words, you can only choose 1 to 9 when filling the array, 0 or 1 time, i.e. no repetition.) Note some pairs have no solution. Later we may replace 9 by 999.

Analysis 1: Instead of poker cards, we can think of 9 boxes in a row, numbered 1 to 9, and we put 0 or 1 bean in each of the boxes, to create an array.

Ashish pointed out the "shift" operation. If we shift 2 beans opposite ways then sum remains. Once we have one "good" array, we can shift the 2 outermost beans further out to the limit…

Analysis 2: I feel this is dynamic programming

Analysis 3: start with a smaller deck of cards — 1/2/3/4/5

Observation 1: if COUNT > 4.5 (i.e. 9/2), then the equivalent problem of (45-SUM, 9-COUNT) is probably simpler.

Observation 1: COUNT=2 is easy.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s