## McNugget Numbers, Revisited

### April 13, 2012

We begin with a brute-force solution that generates all possible combinations of McNuggets and discards those that don’t work; we use list comprehensions from the Standard Prelude:

```(define (mcnugget-list n)   (list-of (list a b c)     (a range (+ (ceiling (/ n 6)) 1))     (b range (+ (ceiling (/ n 9)) 1))     (c range (+ (ceiling (/ n 20)) 1))     (= (+ (* 6 a) (* 9 b) (* 20 c)) n)))```

```> (mcnugget-list 100) ((0 0 5) (1 6 2) (4 4 2) (7 2 2) (10 0 2))```

We take a dynamic programming approach to the problem of counting the ways to form McNugget Numbers without enumerating them. Set up a matrix with n+1 columns numbered 0 to n and 4 rows for sizes of 0, 6, 9 and 20 McNuggets. The first row has 0 in every column except column 0, which gets a 1, as there is one way to count 0 McNuggets. Each subsequent row is filled from left to right, with each cell equal to the sum of the cell above and the cell k columns to the left, where k is the size of the current McNuggets box, either 6, 9 or 20; note that cells in the first k columns are the same as the cells in the row above. When all the columns are filled in all the rows, the right-most value on the last row is the desired result. As a practical matter, because each row is filled left-to-right based on the row above, it is only necessary to keep a single row in memory. Here’s the code:

```(define (mcnugget-count n)   (let ((cs (make-vector (+ n 1) 0)))     (vector-set! cs 0 1)     (do ((xs (list 6 9 20) (cdr xs)))         ((null? xs) (vector-ref cs n))       (do ((x (car xs) (+ x 1))) ((< n x))         (vector-set! cs x           (+ (vector-ref cs x)              (vector-ref cs (- x (car xs)))))))))```

```> (mcnugget-count 1000000) 462964815```

This is exactly the same algorithm as the classic problem of counting the number of ways to make change for a given amount, given a list of available coins. The only difference is to give the list of coins as an input to the problem instead of fixing the list as [6, 9, 20]:

```(define (counts xs n)   (let ((cs (make-vector (+ n 1) 0)))     (vector-set! cs 0 1)     (do ((xs xs (cdr xs)))         ((null? xs) (vector-ref cs n))       (do ((x (car xs) (+ x 1))) ((< n x))         (vector-set! cs x (+ (vector-ref cs x)           (vector-ref cs (- x (car xs)))))))))```

```> (counts '(6 9 20) 1000000) 462964815 > (counts '(1 5 10 25 50 100) 100) 293 > (counts '(1 2 5 10 20 50 100 200) 200) 73682```

Thus, there are 5 ways to form the McNugget Number 100, 462964815 ways to form the McNugget Number 1000000, 293 ways to make change for a US dollar, and 73682 ways to make change for two British pounds sterling.

You can run the program at http://programmingpraxis.codepad.org/ZmjVOjQu.

Pages: 1 2

### 9 Responses to “McNugget Numbers, Revisited”

1. […] today’s Programming Praxis exercise, our goal is to calculate the number of ways a number can be expressed […]

```import Control.Monad.Identity

mcNuggetCount :: Num a => [Int] -> Int -> a
mcNuggetCount xs n = foldl (\a x -> fix \$
zipWith (+) a . (replicate x 0 ++)) (1 : repeat 0) xs !! n

main :: IO ()
main = do print \$ mcNuggetCount [6,9,20] 1000000 == 462964815
print \$ mcNuggetCount [1,5,10,25,50,100] 100 == 293
print \$ mcNuggetCount [1,2,5,10,20,50,100,200] 200 == 73682
```
3. Brikesh Kumar said

Problem: Find all possible combination of x,y,z for which
6x + 9y+ 20z = 100 (or P as input)
Sol: Compute Possible values range of x,y,z. This is the quotient of p divided by 6,8,20
In the above example
x = {0-13}
y= {0-11 }
z ={0-5}
Compute the combination by brute force:

List<tuple> result = new List<tuple>
for(int x= 0; x<= 13; x++)
{
for(int y = 0; y <= 11; y++)
{
for(int z =0; z <= 5; z++)
{
int number = 6x + 9y + 20z;
//put 100 as input variable
if( 100/number ==0)
{
}
else
continue;
}
}
}

4. Brikesh Kumar said

Not a very good algorithm. Looks like a cubic Algorith O(3). Will work to improve it.

5. List result = new List
for(int x= 0; x<= 13; x++)
{
for(int y = 0; y <= 11; y++)
{
for(int z =0; z <= 5; z++)
{
int number = 6x + 9y + 20z;
//put 100 as input variable
if( number ==100)
{
}
else
continue;
}
}
}

6. Here’s an O(n) solution, that probably can be reduced to a closed form with some more work. However, Remco’s solution above is much more beautiful :-)

```typedef signed long long sll;
sll mcnuggetnum(int n) {
// 6*x+9*y+20*z = n.
sll s = 0;
// 3(2x+3y) = n-20z ==> z === 2n (mod 3).
for(int z = (2*n)%3, z_lim = n/20; z <= z_lim; z += 3) {
// Similarly, 2x+3y = (n-20z)/3 = u. Take mod 2.
int u = (n-20*z)/3;
s += (u/3 + 2 - (u%2))/2;
}
return s;
}
```
7. Dynamic Programming

```
target=10**6
coins=[6,9,20]
ways=+*target
for coin in coins:
for i in range(coin,target+1):
ways[i]+= ways[i-coin]

print ways[target]
```
8. sibendu dey said

#include

int mc_check(int);
void com_mc(int);

void main() {
int number;
clrscr();
printf(“Enter Number to be checked \n”);
scanf(“%d”,&number);
if(mc_check(number)==1) {
com_mc(number);
}
else {
printf(“Not an McNugget”);
}
getch();
}

int mc_check(int check) {
int i,flag=1;
if( check%6==0 || check%9==0 ||check%20==0 || (check-20)%6==0 || (check-20)%9==0 || (check-9)%20==0 || (check-9)%20==0 || (check-6)%9==0 || (check-6)%20==0 )
return flag;
else
return 0;
}

void com_mc(int number) {
int i,j,k,flag1,flag2,flag3;
for(i=0;((flag1=i*6)<=number);i++) {
for(j=0;((flag2=j*9)<=(number-flag1));j++) {
for(k=0;((flag3=k*20)<=(number-flag1-flag2));k++) {
if((i*6+j*9+k*20)==number)
printf("Combination:%d*6+%d*9+%d*20\n",i,j,k);
}
}
}
}

9. This is an intuitive yet slow python implementation:

```def mcnugget(n):
return len([(i,j,k) for i in range(n/6+1) for j in range(n/9+1) for k in range(n/20+1) if i*6 + j*9 + k*20 == n])
```