Epic Systems Interview Question
I seriously can't understand how someone can solve this during interview without knowing Frobenius problem n=3 formula... What is this questions trying to test? How better we rememeber formulas???? :-S
I agree with you that it looks like a very bad question for a programming job interview.
Perhaps getting the candidate to write code to figure out the answer was the intent of the question?
No, they just want you to check if the numbers are relatively prime or not, and answer 'YES' or 'NO'. For more, take a look at Schur's theorem.
A McNugget number is a positive integer that can be obtained by adding together orders of McDonald's® Chicken McNuggetsTM (prior to consuming any), which originally came in boxes of 6, 9, and 20. All integers are McNugget numbers except 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43. The value 43 is the number after which any number can be represented as the combination of 6,9 or 20. Therefor n=43
The Number N after we can buy any number of Chicken Nuggets is 43
I will divide all no's in to 3 sets 3n,3n+1 and 3n+2.
If we look at 6 - 3n,9 - 3n and 20 - 3n+2
Now we can generate any 3n Series from 6 to infinity .....so 3 is the no that is not possible
for 2n+2 series..we can generate any 3n+2 no starting from 26 (20 +6 (since 6 is the least no) )....Highest number is 23.
The problem is 3n+1 series..first no that is possible in this series is 20+20 = 40...From 46 onwards we can all the numbers in this series....so we are left with 43...
So 43 is the Highest number beyond which we can but any number of Nuggets using 6,9 and 20.... :)
The bad numbers (number T you can't find integer solution for 6x+9y+20z=T) after 20:
- chao October 03, 200921, 22, 23, 25, 28,
31, 34, 35, 37,
41, 43.
And after that, every number is good. So N=44.
(Note: only need to check 6 consecutive numbers.)