Fog Creek Software
Discussion Board

Nuggets - incorrect solution?

This is my first time reading the techinterview puzzles section. I read through the "nuggets" puzzle which paraphrases like this:

"You can buy chicken nuggets in 6, 9, and 20-pack sizes. Is there a number N such that for all numbers bigger than or equal to N, you can buy precisely that number of nuggets?"

The solution given on the nuggets web page seems incorrect to me. It arrives at a number, 43, using some table method, but I think misses the larger picture.

This puzzle is about factors of a number. Is there a number N, such that all numbers greater or equal to N are always factorable by 6, 9, or 20? I say NO - all prime numbers are examples. As primes are only factorable by one and themselves, they are not factorable by 6, 9, or 20. Modern cryptography relies on very very large prime numbers, so people are always looking for larger and larger ones.

Am I possibly missing something in how the question is phrased, or is the posted solution incorrect?

Kelsey Foley
Monday, June 21, 2004

You're allowed to buy nuggets in combinations. So, if you want  89 nuggets, you can buy a 20-pack, seven 9-packs, and a 6-pack.

Ham Fisted
Monday, June 21, 2004

Just a comment:
the answer is 44. 43 is the last number you can not compose as a sum of 6,9 and 20.

Wednesday, June 23, 2004

Factorization is multplication, buying nuggets is addition, so the primes-example doesn't apply.

Thomas van Dijk
Saturday, September 11, 2004

*  Recent Topics

*  Fog Creek Home