McNugget Numbers, Revisited

April 13, 2012

We studied McNugget Numbers in a previous exercise. You may recall that McDonald’s Restaurants sell Chicken McNuggets in meal sizes of 6, 9 or 20 nuggets, and a McNugget Number is a number that can be formed by some combination of 6, 9 and 20. For instance, 100 is a McNugget Number because 100 = 5 ·20.

The previous exercise asked you to find the list of numbers that cannot be formed by some combination of 6, 9 and 20; those numbers, which are the Non-McNugget Numbers, are 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 and 43. Today’s exercise asks you to count the ways in which a McNugget number can be formed; for instance, you can form the number 100 in 5 different ways: 100 = 0 · 6 + 0 · 9 + 5 · 20 = 1 · 6 + 6 · 9 + 2 · 20 = 4 · 6 + 4 · 9 + 2 · 20 = 7 · 6 + 2 · 9 + 2 · 20 = 10 · 6 + 0 · 9 + 2 · 20.

Your task is to write a program that calculates the number of ways a number can be expressed as a McNugget Number, and to use your program to calculate the number of ways to express one million as a McNugget Number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

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 [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2012/04/13/programming-praxis-mcnugget-numbers-revisited/ for a version with comments):

    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)
    {
    Add(x,y,z) to result list;
    }
    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)
    {
    Add(x,y,z) to result list;
    }
    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=[1]+[0]*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])
    

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: