McNugget Numbers

December 9, 2011

At McDonalds’ Restaurants, the Chicken McNugget meals are available in sizes of 6 McNuggets, 9 McNuggets, or 20 McNuggets. A number is a McNugget number if it can be the sum of the number of McNuggets purchased in an order (before eating any of them). Henri Picciotto devised the math of McNugget numbers in the 1980s while dining with his son at McDonald’s, working the problem out on a napkin.

Your task is to determine all numbers that are not McNugget numbers. 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

14 Responses to “McNugget Numbers”

  1. [...] today’s Programming Praxis exercise, our goal is to determine all the numbers that are not McNugget [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2011/12/09/programming-praxis-mcnugget-numbers/ for a version with comments):

    import Data.List
    
    notMcNuggets :: [Integer]
    notMcNuggets = [1..180] \\
        [a+b+c | a <- [0,6..180], b <- [0,9..180-a], c <- [0,20..180-a-b]]
    
  3. [...] response to this challenge McNugget numbers  I wrote C code based on a different approach than exhibited in the LISP solution and obviously [...]

  4. [...] I heard from my friend about the new programming praxis problem I started thinking how to implement the solution. I wrote down the numbers from 1 to 20 and [...]

  5. Python solution along the same lines as the C one, but self-documenting,

    My thinking is described here: http://ctopy.wordpress.com/2011/12/09/mcnugget-numbers-python-solution/

    
    known = [ 0 ]
    i = 1
    consecutive_success = 0
    
    while True:
      if i - 6 in known or i - 9 in known or i - 20 in known:
        known.append(i)
        consecutive_success += 1
        if consecutive_success == 6:
          print "All numbers >=  %d are mcnugget" % (i - 5)
          break
      else:
        print i
        consecutive_success = 0
      i += 1
    
    
  6. nee said

    I’ve tried to make a Haskell solution using somewhat less mathematical knowlegde (for example the one that we only have to check the numbers smaller than 180).

    import Data.List
    mc = mchelp [0] [0] [0]
            where mchelp s@(a:_) n@(b:_) t@(c:_) =  min:mchelp (p s 6) (p n 9) (p t 20)
                   where min = minimum [a+6,b+9,c+20]
                         p (x:l) n = (if x+n==min then id else (x:)) l++[min]
    
    notmc = [1..last $ needed mc] \\ (needed mc)
            where needed (x:l) = x:(if l!!4 == x+5 then [] else needed l)
    

    The ugly function mc calculates the infinite list of McNugget numbers in increasing order. For example the first 50:

    *Main> take 50 $ mc
    [6,9,12,15,18,20,21,24,26,27,29,30,32,33,35,36,38,39,40,41,42,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72]
    

    And notmc gives the solution /it stops if 6 consecutive McNugget numbers are found, because each larger number can be generated easily by adding 6 to them repeatedly/:

    *Main> notmc
    [1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43]
    
  7. nee said

    And a haskell copy of the popular solution of Tomasz Kwiatkowskis:
    [/sourcecode]
    notmc = helper [0] [1..]
    where helper _ [] = []
    helper is (x:xs)
    | length is > 5 && head is – 5 == is!!5 = []
    | otherwise = if any (\a-> elem a is) [x-6,x-9,x-20]
    then helper (x:is) xs
    else x:helper is xs
    [/sourcecode]

  8. Graham said

    Probably not the most efficient solution, but in relatively short Python:

    from itertools import ifilter, imap, product
    print set(xrange(181)) - set(ifilter(lambda s: s < 181,
                                         imap(sum, product(xrange(0, 181, 6),
                                                           xrange(0, 181, 9),
                                                           xrange(0, 181, 20)))))
    

    The use of the procedures from the itertools module ensures no intermediate lists are constructed.

  9. Ashish said

    I still don’t get why 181 or 182 is not a mcnugget number. You it can not summed using 6,9,20

  10. programmingpraxis said

    22*6 + 1*9 + 2*20 = 181

    24*6 + 2*9 + 1*20 = 182

  11. Nelson said

    Java approach:

    public class McNuggetNumber {
    
    	public static boolean check(int num) {
    		int minusSix = num - 6;
    		int minusNine = num - 9;
    		int minusTwenty = num - 20;
    		if (minusSix == 0) {
    			return true; // 6
    		} else if (minusNine == 0) {
    			return true; // 9
    		} else if (minusTwenty == 0) {
    			return true;
    		} else if (minusSix < 0) {
    			return false;			
    		}
    		return check(minusSix) || check(minusNine) || check(minusTwenty);
    	}
    
    	public static void main(String[] args) {
    		for (int index = 1; index < 180; index++) {
    			if (!check(index)) {
    				System.out.println(index);
    			}
    		}
    	}
    }
    
    
  12. Nosayba said

    Please I have a question … How it is determined that all numbers after LCM “180″ are MCNuggets number?

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 631 other followers

%d bloggers like this: