Can you solve this McNuggets Puzzle || Computer Programming Puzzle

Verify your answer of bonus puzzle here :
mathsjavascript.free.fr/froben...
Simply type the values as 9,12,25 and you get the result as 65.
Problem statement:
At McDonald’s you can order Chicken McNuggets in boxes of 6, 9, and 20.
for instance. If you want 32 pieces, then you can buy one box of 20 and two boxes of 6.
But if you want 16, then you won't be able to buy it with any combination.
What is the highest number of McNuggests that cannot be bouhgt with any combination of these boxes?
This Puzzle is algorithm based puzzle. It also has a very interesting mathematical solution. In this video I have explained both the methods.
Algorithmic approach is used for writting computer programs.

[@rupinjeremiah9589]

This is actually the Frobenius number, which mathematically is the largest number for which the Frobenius equation has no solution. This equation was first developed by Sylvester in 1884. So it is a very old problem.

[@rockytechz5477]

Nuggets are 9,12,25 The possible combinations are Since the highest no. Of nuggets in a single box is 25 So we start combinations for above 25 26= nil 27= 9+9+9 30= 9+9+12 33=9+12+12 34=9+25 36=9+9+9+9or 12+12+12 37=25+12 39=9+9+9+12 42=12+12+9+9 43=9+9+25 45=9+9+9+9+9 or 9+12+12+12 46=25+9+12 48= 12+12+12+12 49=25+12+12 50=25+25 51=9+9+9+12+12 52=25+9+9+9 54=9+9+9+9+9+9 55=25+9+9+12 57=9+9+9+9+9+12 58=25+9+12+12 59=25+25+9 60=12+12+12+12+12 61=25+12+12+12 62=25+25+12 63=9+9+9+9+9+9+9 64= 25+9+9+9+12 65=nil 66=12+12+12+12+9+9 67=25+9+9+12+12 68= 25+25+9+9 69=12+12+12+12+12+9 70=25+9+12+12+12 71=25+25+12+9 72=12+12+12+12+12+12 73=25+12+12+12+12 74=25+25+12+12 .... So on by adding 9 Any no. after 74 can be found by adding 9 in numbers 66to 74. So 65 is the highest unachievable combination.

[@dantedante8837]

god i love it when you refer to us as "logical people"

[@ralphschraven339]

Very clever. Both approaches have their own unique merit: you can solve a subset of this type of problem very quickly with number theoretical approaches. If time and space complexity is not of issue, an algorithmic approach is simple and effective. I think there's something pretty about the fact that you cycle through mod 3 using the boxes of 20 to create this kind of perfectly closed "loop" that you can use to identify the largest "unsolvable" number of nuggets. Way more satisfying than my "check a bunch of numbers" algorithm that just "works". Very nice, many thanks for these beautiful puzzles!

[@alandunstan5485]

It all depends on the number of boxes we're allowed to get. No limit was mentioned in the video.

[@bijendersinghshekhawat6842]

Infinite is the answer.

[@9adam4]

We're not limited in the number of boxes we can order. This problem is about which numbers can't be produced no matter how many boxes you get.

[@robertefremov9380]

@@9adam4 does that mean that you can make any number above 43 combining the any amount of those boxes???

[@9adam4]

@@robertefremov9380 Yes! You can choose a number like 1,841 nuggets and there's a box combination for that.

[@robertefremov9380]

@@9adam4 Wow! thank you

[@mahesh2077]

Cool Algorithm

[@phuzo3320]

I love ur every video .....so much useful ....

[@LOGICALLYYOURS]

Thanks Mahima... glad to know that you found them helpful... get ready for the new puzzle.

[@malahalder8534]

Amazing

[@kartikeysharma5180]

nice good job

[@Crockist]

I took a slightly different approach. I am aware that numbers divisible by 3 will have a digital root divisible by 3: 3, 6, or 9. Subtracting 20 from any value decreases the digital root by 2. If you have a value 41 or over, you will have the digital root of your original number in addition to at least two other digital roots from integers resulting from subtracting by 20. For example, 41, 21, and 1 have digital roots 5, 3, and 1, respectively. With these 3 numbers possible, there are a limited amount of digital root combinations, all of which contain at least one digital root divisible by 3. Overlooking the fact that satisfying the number 3 alone is impossible, I incorrectly concluded 38 as the smallest number. However, 43 is clearly an exception in my formula. I have a feeling this formula will work best with the bonus problem presented at the end of the video. I will give this a shot!

[@yurenchu]

Boxes with values of 9, 12 and 25: Every multiple of 3 greater than or equal to 18 can be created either as a multiple of 9, or as 1x12 + multiple of 9, or as 2x12 + multiple of 9. Every n = 1 mod 3 greater than or equal to 43 can be created as 1x25 + "multiple of 3 greater than or equal to 18" Every n = 2 mod 3 greater than or equal to 68 can be created as 2x25 + "multiple of 3 greater than or equal to 18" ==> every number greater than or equal to 68 can be created. What about numbers less than 68? 67 = 1x25 + 2x12 + 2x9 66 = 1x12 + 6x9 = 4x12 + 2x9 65 = 2x25 + 15, which cannot be created. Conclusion: Highest non-McNugget number is 65 .

[@sushantyadav7806]

I given answer by algorithmic and got correct

[@050138]

I used a combined approach of your mathematical and algorithmic while solving and ended up with right answer 43.... Felit my approach was more rigorous Same logic to find 5 consecutive numbers ie if N number of nuggets can be formed by combination of the three, i.e N = 6(x) + 9(y) + 20(z) then N+1 to N+5 should be formed too by other combinations (the trick is to see how the numbers 1 to 5 can be formed in combinations of multiples of 6, 9 and 20 Eg. 1 = 30 - 9 - 20, 2 = 20 - 18, It is easy to see that with atleast 1 box of 6, 2 boxes of 9 and one box of 20, all these combinations can be generated with only additions and not subtraction terms.... Hence minimum needed is 6 + 9 + 9 + 20 = 44

[@ryanpatel2001]

How do you find out that you need 1 box of 6, 2 boxes of 9 and 1 of 20?

[@bhavyayadav6186]

65..nice problem..

[@minhcongnguyen5917]

Well, similar to the original problems, from 9's and 12's we can make every multiple of 3 that are greater than 15, but not 15. So the answer is 25x2+15 = 65

[@Krysslander]

I think I'm only hungry....

[@maruthasalamoorthiviswanat153]

Excellent puzzle Sir. Really beautiful creation.

[@abrarulhaqshaik]

Answer for Q. at last is 65 Coders..... here's a O(n^3) python coded algorithm- ------------------------------------------------------ li=[] for i in range(100): for j in range(100): for k in range(100): li.append(i*25+j*12+k*9) print(max(set(list(range(100)))-set(li))) ------------------------------------------------------ 1. So yeah you can change the size of nugget's box in the basic operation like ex. i*20+j*9+k*6 as given in the video which also gives 43 as answer... 2. Why 100 in the ranges? You can put any number, but put it wisely as this decides the required maximum impossible nuggets number. P.S. Yes, I want more deduced algorithm in terms of time complexity!! Looking forward to it 😁😁😊.

[@LOGICALLYYOURS]

Thanks Abrar for putting your efforts in writing this piece of code. I have never used python, but I'll definitely run this code.. also will try with various combinations.

[@abrarulhaqshaik]

@@LOGICALLYYOURS Thanks for your content too sir!! But I'm quiet not satisfied with the code, coz it takes too much time yk O(n^3), and if there were more than 3 boxes, then likewise my code would've contained those many loops which eventually again increases time complexity. Mathematically, I should still improve the code with your mentioned algorithmic method in the video. Hope it works fine. P.S. Hopefully should watch entire videos of your channel during this boredom time 😂

[@fardinahsan2069]

The problem with this algo is that u have to guess the range, thus if you were trying to make it for a general case, you'd be in trouble.

[@abrarulhaqshaik]

@@fardinahsan2069 yes, indeed.

[@logitrikkmathematicstricks9694]

#include #include using namespace std; int main() { int n=3,sum=100,i,j,temp,a[]={9,12,25}; int dp[sum+1]; dp[0]=0; for(i=1;i

[@prathwik0]

65 We can form a series of 9 starting from 66

[@leif1075]

He doesnt specify if the maximum number ofnboxes you can,buy is three or not..of not the correct answer is actually infinity..

[@leif1075]

Exactly so the answer is NOT 43..69 AND 67 ARE ALSO IMPOSSIBLE PLEASE CORRECT THIS..65 IS NOT CORRECT EITHER..THE ANSWER IS INFINITY

[@9adam4]

@@leif1075 You can buy as many boxes as you want. 67 = 25 + 12 + 12 + 9 + 9

[@R.a.t.t.y]

If you buy a box of 20, three boxes of 6 and three boxes of 9 nuggets, you will get 65 nuggets

[@venugarg6991]

@@somebody700 ya after 43 any no can be made from these three so ans is 43

[@p.zansei3280]

Thank you for the amazing amazing interactive puzzle Ammar! Watching your videos helps me greatly to exercise my mind before a new semester :D I'm happy to have found the answer with the tools you introduced me to: (=65) using only a pencil, paper, and the algorithm. Thanks again!

[@aculasabacca]

not the only one that can't do it. Whew.

[@mathsx5887]

I did the mathematical one

[@gandhamsanthosh388]

How do you frame these questions??

[@disguisedhell]

This is a real life problem with mcnuggets

[@chandra_955]

@@disguisedhell Lol

[@sutirthmahakul2737]

Infinity

[@manik_.a]

Is that any shortcut to finding the first consecutive number

[@yurenchu]

With boxes of 6, 9 and 20 McNuggets: Every even number greater than or equal to 40 can be created either as a multiple of 6, or as 1x20 + multiple of 6, or as 2x20 + multiple of 6. Every odd number greater than or equal to 49 can be created as 1x9 + "even number greater than or equal to 40". So that means that every number (even or odd) greater than or equal to 49 can be created, and hence that the highest non-McNuggets number is less than 49.

[@pableraspfgpfg468]

LCM(6,9) + LCM(6,20) - 6 - 9 - 20 = 43

[@mja351]

The highest number of nuggets that cannot be bought is one more than the restaurant has in its freezer

[@danibarack552]

The algorithmic approach is kinda brute-forcey

[@nightfall37]

10 to the infinite power + 43 could not be purchased either though. The question is oddly framed.

[@thokari5848]

Using boxes of 6,9, and 20, any positive integer above 43 can be formed, e.g. 10043 Nuggets can be bought in 7 boxes of 9, plus 499 boxes of 20, all the way up to infinity, which includes all numbers 10^x + 43, where x is also a positive integer, and it's easy to see that this is also a general solution, i.e. (10^x - 1) * 20 + 7 * 9.

[@iyyappane7352]

yes well 65 is the Right answer✌

[@benitto_rajf6178]

If you have the code for this problem send it

[@jovansingh2134]

20+ 9+ 9+ 6+ 6+ 6+ 9= 65

[@TJTrickster]

@@jovansingh2134 numbers were 9 12 and 25

[@avinashtamarapalli7659]

1st view and 1st comment

[@JohnSmith-bb1cl]

You can solve using algebra 6x+9y+20z=total nuggets simplifies to 3(2x+3y)+20z where x,y,z integer inc 0, so total is always a multiple of 3 plus multiple of 20 but 2x+3y cannot equal 1 when x and y integers inc 0 so total not achieveable is 20u+3 where u integer inc 0 , u cannot be 3 or more in this not achieveable formulae, otherwise 20u+3 is 3(20+1) which is same as first formula with z =0, x=0 , y=7, u cannot also be 4 or greater as this becomes 20+3(20+1) which is also orginal formula with z=1, x=0, y=7 same for any other value u greater than 4 so u max is 2 which means max unachieveable is 2x20+3 = 43

[@suprajach6249]

43

[@destoyerx-brawlstars6847]

65

[@imGool]

Is there a shortcut to find the set of consecutive numbers?

[@pableraspfgpfg468]

LCM(6,9) + LCM(6,20) - 6 - 9 - 20 = 43

[@sabyasachirimpa]

65 is the answer, yes yes yes i got it, wow😁👏

[@abdulwaquar5255]

20 + 45(multiple of 3)

[@TheRandomizerYT]

My answer is.... No I cannot...

[@TheRandomizerYT]

Please check out my small channel as well...

[@jatin161]

onn the riddle with 9 12 and 25 minium is 47

[@HRO-n-SLO]

I thought it was 4, 6, and 10.

[@Ryarios]

Define ‘impossible’. There are lots of large numbers that can’t be bought if nothing more than the fact that there isn’t enough money or chicken...

[@yurenchu]

If there's no restriction of time then any finite number can be bought (sooner or later). (If there's not enough money or chicken today, then you may buy part right now and more next week, when there's more money or chicken.)

[@aryanshrajsaxena6961]

Sir what is the answer of the last problem?

[@LOGICALLYYOURS]

Aryansh... the answer should be 65. Below is the algorithmic listing of all possible combinations. The number '65' is the highest value not available with any combination. We should list down the combinations until we get 9 consecutive available numbers (then for the next number and ahead we can simply keep on adding 9). 9,12,25 9 9 12 12 18 9,9 21 9,12 24 12,12 25 25 27 9,9,9 30 9,9,12 33 9,12,12 34 9,25 36 12,12,12 or 9,9,9,9 37 12,25 39 9,9,9,12 42 9,9,12,12 43 9,9,25 45 9,12,12,12 or 9,9,9,9,9 46 9,12,25 48 12,12,12,12 or 9,9,9,9,12 49 12,12,25 50 25,25 51 9,9,9,12,12 52 9,9,9,25 54 9,9,12,12,12 55 9,9,12,25 57 9,12,12,12,12 58 9,12,12,25 59 9,25,25 60 12,12,12,12,12 61 12,12,12,25 62 12,25,25 63 9,9,9,9,9,9,9 64 9,9,9,12,25 66 9,9,12,12,12,12 (57+9) 67 9,9,12,12,25 (58+9) 68 (59+9) 69 (60+9) 70 (61+9) 71 (62+9) 72 (63+9) 73 (64+9) 74 12,12,25,25 75 (66+9) and so on....

[@abhimanyugupta9049]

65, though it took a long time to reach this by making all the combinations. What's the shorter or optimised method of applying the algorithm ?

[@venkateshv626]

Did u really get it, how about this combination, 65=20+6+6+6+9+9+9.😂😂

[@yurenchu]

It's shorter to first establish an upper bound, and then work your way down from that bound. Every multiple of 3 greater than or equal to 18 can be created either as a multiple of 9, or as 1x12 + multiple of 9, or as 2x12 + multiple of 9. Every n = 1 mod 3 greater than or equal to 43 can be created as 1x25 + "multiple of 3 greater than or equal to 18" Every n = 2 mod 3 greater than or equal to 68 can be created as 2x25 + "multiple of 3 greater than or equal to 18" ==> every number greater than or equal to 68 can be created. So the highest non-McNugget number must be less than *68* (= upper bound). 67 = 1x25 + 2x12 + 2x9 66 = 1x12 + 6x9 = 4x12 + 2x9 65 = 2x25 + 15, which cannot be created -- Bingo!

[@josemaestro]

59 nuggets cannot be bought by combinations of 20, 6, 9

[@chillmode1881]

What if I want 1000 mc nuggets? Now I need 500 boxes of 20.

[@vishalmor6353]

57

[@omkarkulkarni5932]

Ans. Is 59

[@cricketcoachingforchildren4446]

Classical problem.

[@sirnikkel6746]

Infinite?

[@beardeddadbod3923]

You can buy them in 4,s aswell

[@brianmagicman3556]

No you can't

[@beardeddadbod3923]

Happy meals

[@brianmagicman3556]

@@beardeddadbod3923 That's different You're not buying the actual nuggets in 4's, which is what you said

[@TJTrickster]

We are at McRonald's not McDonald's

[@susmitapodder4081]

Infinity or sixty

[@emem2756]

83? Or did I miss some assumption?

[@lab483]

9,9,9,9,9,9,9,20

[@dhiraj.govindvira]

Given value of N and K (N>=2 , K>=1) From Range K , N + K -1 How many number you can't aachive ??? Ex . N = 3, K = 3 Range ( 3 , 5 ) So by combination of 3 , 4 , 5 You cant aachive 1 and 2 so ans is 2 ( total no. Cant aachive )

[@induchandrakar6649]

56

[@aydenhk9937]

1093

[@jogenwaikhom8715]

97

[@drkiranmahabole1836]

I touch ed the video caz it had nuggets written 😂😂😂😂

[@talhaaman3402]

My solution is 41

[@techwellness6142]

Can you show if we can get 34 ? My ans is 34 , but your saying 43

[@LOGICALLYYOURS]

Question says what's highest number can't be ordered. Now 43 is higher than 34, so you can eliminate 34.

[@mohdfaizan1939]

@@LOGICALLYYOURS then what about 46 , it's not the right question

[@surajjayswal8083]

@@mohdfaizan1939 20+20+6

[@jain.j]

Over the head!

[@paulobouhid6648]

I can buy *43* nuggets!! At noon, I buy 6 nuggets. Later, I return to the grocery and order 49 nuggets, which I partially pay with the 6 nuggets I bought earlier. Technically, I bought *43 nuggets!!*

[@yurenchu]

No, technically you bought 49 new nuggets, and paid partially with 6 old nuggets. After the transaction, you end up with 49 nuggets (not 43).

[@TJTrickster]

65 is the answer 66=6×9+12 67=25+2×12+2×9 68=2×25+2×9 69=5×9+2×12 70=25+5×9 71=2×25+9+12 72=8×9 73=25+4×12 74=2×25+2×12 I win after about 5 minutes I first thought 58 but 65 was in the proof and I couldn't prove it

[@no.1littlescientist-tamil664]

Answer is 65

[@allwinjoans8023]

65 as a answer

[@kritigoyal3262]

20 +9+9+9+9+9

[@allwinjoans8023]

We use only 9,12,25 number boxes.....

[@martinvanlierop5020]

59. 😀

[@leif1075]

This is unclear and inaccurate..are you limited to three boxes or not?

[@dielegendenvonandor7843]

You are limeted to box values (6 9 20) but you can buy as many as you want

[@b.bharathsai2481]

How can u obtain 77 no. Of nuggets??

[@manishb7072]

5 -9, 2- 6, 1- 20

[@jishnuvr6466]

@@manishb7072 no.s were 9,12 and 15

[@jishnuvr6466]

25+25+9+9+9=77

[@shivamdhiman2844]

Bhai m swiggy karlunga

[@jigyasbaruah7531]

It's 56.

[@seanpribadi7888]

20 + 9 + 9 + 6 + 6 + 6

[@ClickBeetleTV]

@@seanpribadi7888 Or 20 + (6*6)

[@arnabpersonal6729]

Question framing is a bit ambiguous

[@phiefer3]

what's ambiguous about it?

[@neonoir7549]

Awnser 3 Infinete

[@michaelkhouzam]

This one is styoobid

[@thisisnew7694]

65 😁

[@paulobouhid6648]

*20* + 5 x *9*

[@brianmagicman3556]

There's no such thing as McNuggests so the answer is zero (0) !!!!!!!!

[@JawadMohiuddin]

www.mcdonalds.com/us/en-us/product/chicken-mcnuggets-4-piece.html

[@manaalanshath5079]

How could you get 17 pieces?

[@dlevi67]

You can't, but it doesn't matter since 43 is more than 17.

[@anujkothari2134]

Y 91 is not the answer

[@yurenchu]

91 = = 20 + 20 + 9 + 9 + 9 + 9 + 9 + 6 = 20 + 20 + 9 + 9 + 9 + 6 + 6 + 6 + 6 = 20 + 20 + 9 + 6 + 6 + 6 + 6 + 6 + 6 + 6

[@McHrozni]

The solution is easy: it's the largest finite prime number. Or infinite.

[@yurenchu]

The largest finite prime number doesn't exist. And "infinite" is not a number.

[@McHrozni]

@@yurenchu I know, I was trying to show how misplaced the puzzle question is..

[@yurenchu]

@@McHrozni The puzzle question isn't misplaced. The correct answer is 43 (as shown in the video).

[@McHrozni]

@@yurenchu the correct answer to a similar question is, at any rate.

[@yurenchu]

@@McHrozni What are you talking about? The question in the video is: _At McDonald's, you can order chicken nuggets in boxes of 6, 9 and 20. What is the highest number of McNuggets that cannot be bought with any combination of these boxes?_ The correct answer is 43. There's nothing wrong with the question.

[@OrenLikes]

cannot reach 3, 6, and 15. 2*25+15=65.

[@BSS_00]

The answer should be The highest prime number,comment if you agree

[@abrarulhaqshaik]

Well answer for the last Q. (65) isn't a prime so I disagree

[@yurenchu]

There is no such thing as "the highest prime number".

[@chillmode1881]

The question is stupid. the real answer is infinite.

[@argsahoo]

I guess it's 47

[@seanpribadi7888]

20 + 9 + 9 + 9

[@paulobouhid6648]

*20* + 3 x *9*

[@riyaramesh1150]

What about 48

[@stalwart08]

9*4 n 6*2

[@KishanKumar-hu2mm]

Answer is 65 ....wow i got it 18 minutes....

[@naomipasirpanjang7045]

Then show me how to get 63

[@naomipasirpanjang7045]

With 6,9 and 20

[@RicardoFernandez-mr5cw]

7 * 9

[@knight.2049]

9+9+9+9+9+9+9=63

[@yurenchu]

63 = = 7 x *9* = 5 x *9* + 3 x *6* = 3 x *9* + 6 x *6* = 1 x *9* + 9 x *6* In other words, you can get 63 McNuggets with either seven, eight, nine or ten boxes.

[@anonymouslyfamous6102]

65

[@balajik7659]

53

[@kunwarharshitshah5663]

65

[@nruharivishwanath1102]

57

[@fascination1461]

Yes but it is not highest number I think it is 65

[@paulobouhid6648]

*57* = 5 x *9* + 2 x *6*

[@paulobouhid6648]

@@fascination1461 *65* = *20* + 5 x *9*

[@santanunath3744]

What about 48

[@BCSEbadulIslam]

65

[@jadenruanes1858]

43

[@johnkumarmalluvalasa4643]

65

[@mohitverma4909]

65

[@ranadheerreddyguduru2766]

65

[@shivanshsingh7761]

65

[@josemaestro]

65 = 1 * 40 + 1 * 6 + 1 * 9

[@Kirubhas_Shankar]

65

[@Kirubhas_Shankar]

@@chandrahasdewangan2331 We should use 12,9 and 25 NOT 20.

[@chandrahasdewangan2331]

@@Kirubhas_Shankar Ohh sorry!! I got a bit confused!!

[@iyyappane7352]

12+12+12+12+9=57