The McNuggets Problem
My son, now 25, was a McNuggets fan. Can you blame him? They’re delicious. He’s always been into numbers and puzzles, so I introduced him to the McNuggets problem when he was about 10.
This classic puzzle was a fun way to keep him occupied and teach him programming. The problem is simple: McDonald’s used to sell Chicken McNuggets in 6, 9, and 20 packs. What is the largest number of McNuggets you cannot buy using these package sizes?
Clear as mud?
You’re at McDonald’s with an offspring. Said kid says, “I want 13 McNuggets.” You can buy a 6-pack and a 9-pack, but you can’t buy a 13-pack. Nor can you buy a 7-pack, 8-pack, 11-pack, or 14-pack. But you can buy a “15-pack”, because 15 = 6 + 9.
What’s the largest number of McNuggets you can’t buy up to, say, 100 nuggets? Even the best eater can’t eat 100 McNuggets in one sitting so that seems reasonable.
The problem can be solved using a simple brute-force approach, where we try all possible combinations of the three pack sizes and check which numbers can be made. We then find the largest number that can’t be made.:
100 DIM NU(100)
110 FOR SI = 0 TO INT(100/6)
120 FOR NI = 0 TO INT(100/9)
130 FOR TW = 0 TO INT(100/20)
140 N = SI*6+NI*9+TW*20
150 IF N <= 100 THEN NU(N) = 1
160 NEXT TW
170 NEXT NI
180 NEXT SI
185 REM PRINT OUT WHICH NUMBERS CAN BE MADE
186 PRINT "POSSIBLE NUMBERS UP TO 100:"
187 FOR I = 1 TO 100
188 IF NU(I) = 1 THEN PRINT I;
189 NEXT I
190 PRINT: PRINT "----"
191 REM FIND THE LARGEST NUMBER THAT CAN'T BE MADE
192 FOR N = 100 TO 1 STEP -1
193 IF NU(N) <> 1 THEN PRINT "MAXIMUM NON-MCNUGGETS NUMBER IS: ";N: GOTO 200
194 NEXT N
200 END
The approach
Step 1: Initialize Array to Track Possible Numbers
Line 100 initializes an array NU with 101 elements (0 through 100) to track which numbers can be exactly made using combinations of the pack sizes. The array marks a number as possible (1) if it can be formed.
Step 2: Generate Combinations of Pack Sizes
Lines 110-180 are nested loops for each pack size (6, 9, and 20). The loops iterate through the possible number of packs for each size that could contribute to totals up to 100. The variable names SI, NI, and TW represent the counts of 6-pack, 9-pack, and 20-pack sizes, respectively. For each combination of packs, line 140 calculates the total number of nuggets (N) that can be obtained.
Line 150 checks if the total N is within our range of interest (up to 100). If so, it marks the corresponding index in the NU array as 1, indicating this total can be achieved.
Step 3: Identify and Print Possible Numbers
Lines 185-189 print out all numbers up to 100 that can be achieved with the given pack combinations. It iterates through the NU array and prints the index numbers that are marked as possible.
Step 4: Find the Largest Number That Can’t Be Made
Lines 191-193 search for the largest number that cannot be made with the available pack sizes, starting from 100 and counting down. It checks the NU array for the first index not marked as 1 (indicating it’s impossible to achieve that total with the given packs) and prints this number as the “maximum non-McNuggets number”.
Run it
Python version
Here’s a Python version of the same code. I like the use of nested loops because it’s easy to understand how the problem is being solved.
# Initialize a list to track which numbers up to 100 can be made
possible_numbers = [0] * 101 # We use 101 because list indices go from 0 to 100
# Loop through all possible combinations of 6, 9, and 20 packs
for six_pack in range(0, 101, 6):
for nine_pack in range(0, 101, 9):
for twenty_pack in range(0, 101, 20):
# Calculate the total number of nuggets for this combination
total = six_pack + nine_pack + twenty_pack
# Mark this number as possible if it's 100 or less
if total <= 100:
possible_numbers[total] = 1
# Now, find the largest number that can't be made
# We start from the end of the list and go backwards
max_non_mcnuggets_number = None
for i in range(100, 0, -1):
if possible_numbers[i] == 0:
max_non_mcnuggets_number = i
break
# Print out which numbers up to 100 are possible
print("Possible numbers up to 100:")
possible_list = [i for i, possible in enumerate(possible_numbers) if possible]
print(possible_list)
# Print the largest number that can't be made
print("\nMaximum non-McNuggets number is:", max_non_mcnuggets_number)
We could also use a set to track the possible numbers, which would make the code a bit more concise:
# Initialize a set for possible numbers
possible_numbers = set([0]) # Start with 0 as a possible number
# Iteratively add each pack size to existing numbers to find new totals
for pack_size in [6, 9, 20]:
for existing in list(possible_numbers):
# Add new totals up to 100
total = existing + pack_size
while total <= 100:
possible_numbers.add(total)
total += pack_size
# Find all numbers up to 100 that are possible
all_numbers = set(range(1, 101))
impossible_numbers = all_numbers - possible_numbers
max_non_mcnuggets_number = max(impossible_numbers)
# Print the possible numbers up to 100 and the maximum non-McNuggets number
print("Possible numbers up to 100:")
print(sorted(possible_numbers))
print("\nMaximum non-McNuggets number is:", max_non_mcnuggets_number)
I’m not sure which of these I like better. You can decide.
You could certainly use itertools to generate the combinations of pack sizes, but I think the nested loops are easier to understand for this problem.
Extra Credit
The McNuggets problem is a fun way to introduce kids to programming and problem-solving. It’s also a great example of how programming can solve real-world problems, even as trivial as counting McNuggets.
Plus, I LOVE tabular data tables on old computers.
Is there a number higher than 43 that can’t be made with 6, 9, and 20 packs regardless of the upper bound? Try it at 500, 1000, 10000… What do you find?
Today, McNuggets are available in packs of 4,6,10,20, and 40. Can you find the largest combination you cannot order today? Why is the answer less straightforward than the original problem that uses 6,9 and 20 packs?
If you implement this yourself, I’d love to see what you come up with. Bonus points if you use a vintage computer, but I’d also love to see implementations in modern systems.