Diophantine Equation
Posted
by swapnika
on Stack Overflow
See other posts from Stack Overflow
or by swapnika
Published on 2010-06-16T04:37:20Z
Indexed on
2010/06/16
4:42 UTC
Read the original article
Hit count: 495
Filed under:
python
Write an iterative program that finds the largest number of McNuggets that cannot be bought in exact quantity. Your program should print the answer in the following format (where the correct number is provided in place of n):
"Largest number of McNuggets that cannot be bought in exact quantity: n"
Hints:
- Hypothesize possible instances of numbers of McNuggets that cannot be purchased exactly, starting with 1
- For each possible instance, called n, 1. Test if there exists non-negative integers a, b, and c, such that 6a+9b+20c = n. (This can be done by looking at all feasible combinations of a, b, and c) 2. If not, n cannot be bought in exact quantity, save n
- When you have found six consecutive values of n that in fact pass the test of having an exact solution, the last answer that was saved (not the last value of n that had a solution) is the correct answer, since you know by the theorem that any amount larger can also be bought in exact quantity
© Stack Overflow or respective owner
