# looping through possible combinations of McNuggets packs of 6, 9 and 20

Roald de Vries downaold at gmail.com
Thu Aug 12 13:04:58 CEST 2010

```On Aug 12, 2010, at 11:33 AM, Paul Rubin wrote:
> Baba <raoulbia at gmail.com> writes:
>> exercise: given that packs of McNuggets can only be bought in 6, 9 or
>> 20 packs, write an exhaustive search to find the largest number of
>> McNuggets that cannot be bought in exact quantity.
>
> Is that a homework problem?  Hint: first convince yourself that a
> largest number actually exists.

Good point. There is actually an upper bound. Let's take 6 packs of
20, that's 120 nuggets.
Now 121 nuggets can be reached by substituting 1 pack of 20 with 2
packs of 6 and 1 pack of 9.
122 = 4*20 + 2*(2*6+9)
123 = 3*20 + 3*(2*6+9)
...
126 = 6*20 + 6
127 = 121 + 6 = 5*20 + (2*6 + 9) + 6
... etcetera.

Now you have to find the largest number below 120, which you can
easily do with brute force (untested):

can_be_bought = [False for i in range(120)]
for twenties in range(6):
for nines in range(14):
for sixes in range(20):
can_be_bought[twenties*20+nines*9+sixes*6] = True
for i in reverse(range(120)):
if not can_be_bought[i]: return i

Cheers, Roald

```