• Vehicles • Fashion • Recipes • Blogs • Hunt • Travels • Sport • Fun • Handmade • IT • Education
Mini-Games
x

x
zakruti.com » Knowledge, science, education » Logically Yours
Can you solve this McNuggets Puzzle Computer Programming Puzzle

Can you solve this McNuggets Puzzle Computer Programming Puzzle

FBTwitterReddit

video description

Rating: 4.0; Vote: 1
Can you solve this McNuggets Puzzle -- Computer Programming Puzzle dragondawg: 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!
Date: 2023-11-15

Comments and reviews: 15


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

reply

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.

reply

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
reply

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!

reply

Here's an implementation of the algorithm in python using dynamic programming.
I believe it runs in O(n)-O(k, where n is the size of the smallest box and k is the number of different box sizes you can order.
def isPossible(n): -
global biggest-
global boxes-
global possible-
if len(possible)>n: -
return possible[n]-
for b in boxes: -
if b

reply

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!

reply

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 )

reply

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.
reply

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! -
reply

#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

reply

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
reply

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?

reply

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.
reply

This is something related to frobenius number. If you are interested in maths then you can check out Vsauce2 video, 'Frobenius'
reply

The highest number of nuggets that cannot be bought is one more than the restaurant has in its freezer
reply
Add a review, comment






Other channel videos