## Facebook Interview Question for Developer Program Engineers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
9
of 11 vote

The following is my O(1) time complexity, O(1) space complexity implementation in python 3:

``````possibleMcNuggets = [False for i in range(46)]

def McNuggets(n):
if not isinstance(n, int): return False
if n < 0: return False
if n > 45: return True

if False == possibleMcNuggets:
possibleMcNuggets = True
for i in range(46):
if possibleMcNuggets[i]:
if i + 6 < 46: possibleMcNuggets[i + 6] = True
if i + 9 < 46: possibleMcNuggets[i + 9] = True
if i + 20 < 46: possibleMcNuggets[i + 20] = True

return possibleMcNuggets[n]``````

Obviously, for any n larger than or equal to 46, the answer must be True.
(1) With zero package of 20, it is possible to buy 3x McNuggets where x is an integer larger than or equal to 2
(2) With one package of 20, it is possible to buy 3x + 2 McNuggets where x is an integer larger than or equal to 8
(3) With two packages of 20, it is possible to buy 3x + 1 McNuggets where x is an integer larger than or equal to 15

Comment hidden because of low score. Click to expand.
0

for i in range(46):
if possibleMcNuggets[i]:
if i + 6 < 46: possibleMcNuggets[i + 6] = True
if i + 9 < 46: possibleMcNuggets[i + 9] = True
if i + 20 < 46: possibleMcNuggets[i + 20] = True

can be optimzed to do it recursively removing iteration where possibleMcnuggets[i] is false. this is bounded by 46, so can be done in preprocessing stage for more faster execution time.

Comment hidden because of low score. Click to expand.
0

btw, killer thinking.

Comment hidden because of low score. Click to expand.
0

hey, i understood your logic to check for number beyond 46..... but how did you come up with the number 46?

Comment hidden because of low score. Click to expand.
0

Awesome solution! how did you come up with > 45? I know it is 3*3*5 from each numbers but I have no idea why it works?

Comment hidden because of low score. Click to expand.
7
of 11 vote

``````public class McNuggets {

public static boolean canBuyNMcNuggets(int n) {
return n >= 0 && (n == 0 || n % 6 == 0 || n % 9 == 0 || n % 20 == 0 || canBuyNMcNuggets(n - 6) || canBuyNMcNuggets(n - 9) || canBuyNMcNuggets(n - 20));
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

def McNuggets(n):
ret = False

if (n < 1):
return False;
if ((n % 6 == 0)or(n % 9 == 0)or(n % 20 == 0)):
return True
if (ret == False and n > 20):
ret = McNuggets(n - 20)
if (ret == False and n > 9):
ret = McNuggets(n - 9)
if (ret == False and n > 6):
ret = McNuggets(n - 6)
return ret

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Dude...

This works well in Python, just arrange the indentation and it will be ok. The grader outputted correct

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Neat solution!

Comment hidden because of low score. Click to expand.
-1
of 1 vote

But what if you want 39?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

elegant code but horrible space complexity

Comment hidden because of low score. Click to expand.
1
of 1 vote

It will take 3^N time which is bad. You can use dynamic programming instead.

This recurrence relation could be used
P(m): True or False for is it possible to get m McNuggets.
P(m) = P(m-6) | P(m-9) | P(m-20).
P(n) would contain the final output.

O(n) time complexity and O(n) space complexity!

Comment hidden because of low score. Click to expand.
0

Time complexity with recursion is exponential. With DP it's not linear but pseudo-polynomial.

Comment hidden because of low score. Click to expand.
2
of 2 vote

Oneliner in C:

``````int mc(int n) {
return n >= 0 && (n == 0 || mc(n-6) || mc(n-9) || mc(n-20));
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

boolean McNuggets(int n)
{
boolean ret = false;

if (n < 1)
return false;

if ((n % 6 == 0) ||
(n % 9 == 0) ||
(n % 20 == 0))
return true;

if (ret == false && n > 20)
ret = McNuggets(n - 20);

if (ret == false && n > 9)
ret = McNuggets(n - 9);

if (ret == false && n > 6)
ret = McNuggets(n - 6);

return ret;
}

Comment hidden because of low score. Click to expand.
0

@Vinod: Why are you posting without running some test cases on your code. Your code fails for even basic cases leave trickier cases aside.

Check your code with n = 33 (20*0 + 9*3 + 6*1)

Comment hidden because of low score. Click to expand.
0

@nitingupta180: Have you tested his code?I bet you haven't.Please check that it works for 33 as well.

Comment hidden because of low score. Click to expand.
0

@anish : I can still see that it is failing for 33. Check once again.

Comment hidden because of low score. Click to expand.
0

nitingupta180:Sorry my bad butit still works.

"@nitingupta180: Are you serious?I double checked for your amusement but this works well.
Just call mcNuggets(33) and check what it returns.
If I trust my machine it returns 1 which I think is right answer."

Comment hidden because of low score. Click to expand.
0

@anish: Ok lets walk through the code.

Call McNuggets(33)
Then it will substract 20 from it.
Call McNuggets(13)
Then it will substract 9 from it.
Call McNuggets(4)
Then it will return false.

Comment hidden because of low score. Click to expand.
0

nitingupta180: nope.That is now how it works.
33 in-turn will get checked with 9, 6
So 33-9 = 24 and (24%6 == 0) return true.

I would suggest you to solve recursion problems more to get good understanding.

Comment hidden because of low score. Click to expand.
0

@anish: I think you are wrong. How it will skip if condition which is checking for > 20 for the first time.

Comment hidden because of low score. Click to expand.
0

why not add some logs and check for yourself?It would really clarify your doubt.I strongly recommend you to not post any further on this and put some logs as below and check.
if (ret == false && n > 20)
ret = McNuggets(n - 20);
printf("n %d\n", n);

Comment hidden because of low score. Click to expand.
0

I just run the code and it is working for 33.
there after failed for:

Call McNuggets(33)
Then it will substract 20 from it.
Call McNuggets(13)
Then it will substract 9 from it.
Call McNuggets(4)
Then it will return false.

it will check 33-9 = 24 and (24%6 == 0) return true.

did u actually run the code?

Comment hidden because of low score. Click to expand.
0

@Anish, dude, you are confidently saying wrong :) For 33, your code should return after (33-20) check. So it will fail.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
1
of 1 vote

does this code work for n=41 which is a combination of(6+6+9+20)...??

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think this problem is similar to Minimum Coin Problem. Given set of coin values. Find minimum no of coins required for a sum. This can be solved easily by dynamic programming.
Code goes like this.

``````int min(int n)
{
int packages[] = {1,9,20};
int size = sizeof(packages)/ sizeof(int);
int sum[n+1] = {INT_MAX};
for(int sum_counter = 1; sum_counter < n+1; sum_counter++)
{
for(int coin_counter = 0; coin_counter < size; coin_counter++)
{
if(packages[coin_counter] <= sum_counter &&
sum[sum_counter - packages[coin_counter]] < sum[sum_counter])
{
sum[sum_counter] = sum[sum_counter - packages[coin_counter]] + 1;
}
}
}
return sum[n];
}``````

The above code is is for Minimum Coin problem. We have to modify it to handle case where it is not possible and also I have replaced 6 by 1 so that index does not goes out of bound for above program.

Its 12 am. Feeling sleepy.
Just Give a thought to this approach.
Tell me if I am wrong.

Comment hidden because of low score. Click to expand.
0

Yes. Coin change. We don't care if its minimum or not. If we can make change for a given number, we're good. I've posted my solution as a comment.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````# Fast analytical solution using modular arithmetic
def McNuggets(n):
c = -n % 3
n -= c*20
b = n // 3 % 2
n -= b*9
a = n // 6
return a >= 0``````

``````# Degenerate solution, since all large numbers are reachable
def McNuggets(n):
return n not in frozenset((1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43))``````

Comment hidden because of low score. Click to expand.
0

``````c = -n % 3
n -= c*20
b = n // 3 % 2
n -= b*9
a = n // 6
return a >= 0``````

Can you explain how that works? I'm appalled!

Comment hidden because of low score. Click to expand.
0

Clever but unmaintainable code.

Comment hidden because of low score. Click to expand.
0

Sure, don't put this version into production. :)

Both 6 and 9 are divisible by 3. If n is not divisible by 3, then you can't sum to n with any number of just 6's or 9's. You'll need at least 1 or 2 of the 20-count packages. The first line figures out the minimum number of 20-count packages that will be necessary, so that the remaining sum is divisible by 3. In the second line, the n variable is decreased by the number of McNuggets in the 20-count packages.

At that point we know that the value in n is divisible by 3, (because we carefully chose the number of 20-count packages with just that goal in mind). Sometimes that number may not be divisible by 6 though. In that case, we need a minimum of 1 9-count package. So in the third line, we decide whether we need a 9-count package in order to make the remainder evenly divisible by 6. We'll need 0 or 1 9-count packages, but we'll never need more than 1 to make the remaining sum divisible by 6. In the fourth line, we decrease n by the number of McNuggets in the 9-count package, if there is one.

After that, whatever remains in n is divisible by 6, so we can divide to see how many 6-count packages would be needed.

The calculations above will work for any n, and will quickly find the minimum number of 20- and 9-count packages that are needed to arrive at the correct total. However, suppose that n is less than 40, and yet we calculate that we need a minimum of 2 20-count packages to get an exact sum. Those are the cases where it would be impossible to buy to n exactly. For example, if n is 19, then c will be 2 and b will be 1, and a will end up being -5. We would have to buy a minimum of 49 McNuggets just to turn n into something divisible by 6, but that is more than our original target of 19. The algorithm tries to compensate by buying a negative number of 6-count packages. That's why the final line tests to see if a is negative, because that means it is impossible to buy to that count exactly.

A lot of people try dynamic computing on this problem, because it looks similar to the "subset sum" problem, which is NP-complete. But there is a huge difference here: none of the package sizes are negative. That means that an analytic solution is possible. The first version I wrote runs in O(n) time, and the second in O(1) time.

Comment hidden because of low score. Click to expand.
0

Not all large numbers are reachable so the "Degenerate solution" is incorrect. Examples: 3422, 3428, 3431 and so on.

Comment hidden because of low score. Click to expand.
0

No it is not.Please check for frobeius number.With 20,9,6 the last such number is 43.

Comment hidden because of low score. Click to expand.
0

@nitingupta180: Are you serious?I double checked for your amusement but this works well.
Just call mcNuggets(33) and check what it returns.
If I trust my machine it returns 1 which I think is right answer.

Comment hidden because of low score. Click to expand.
0

@anish : I think you replied on wrong post. See for which solution I commented.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Simple DP problem,
Recurrence relation:
Ways(x)=Ways(x-6)+Ways(x-9)+Ways(x-20)

If Ways(n)>0 return true
else return false

Comment hidden because of low score. Click to expand.
1
of 1 vote

Python based recursive solution:

``````def check(n):

if n >= 20:
return check(n - 20) or check(n - 9) or check(n - 6)

if (n >= 9):
return check(n - 9) or check(n - 6)

if (n >= 6):
return check(n - 6)

return n == 0``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

def McNuggets(n):
"""
n is an int

Returns True if some integer combination of 6, 9 and 20 equals n
Otherwise returns False.
"""
ret = False

if (n < 1):
return False;
if ((n % 6 == 0)or(n % 9 == 0)or(n % 20 == 0)):
return True
if (ret == False and n > 20):
ret = McNuggets(n - 20)
if (ret == False and n > 9):
ret = McNuggets(n - 9)
if (ret == False and n > 6):
ret = McNuggets(n - 6)
return ret

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;

bool possible(int sum, int a1, int a2, int a3){
if(sum == 0){
cout<<a1<<" "<<a2<<" "<<a3;
return true;
}
if(sum <6) return false;
return possible(sum - 20, a1, a2, a3+1) || possible(sum - 9, a1, a2+1, a3) || possible(sum - 6, a1+1, a2, a3);
}

int main(){
int sum;
cin>>sum;
possible(sum, 0, 0, 0);
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anyone give me this same code in Python ??

Comment hidden because of low score. Click to expand.
0

``````ef McNuggets(n):
nf = 0
print (n)
ret = False
if n < 1 :
return False
if (n %6 == 0 or n % 9 == 0 or n % 20 == 0):
return True
if n > 20 :
ret = McNuggets(n-20)
elif n > 9 :
ret = McNuggets(n-9)
elif n > 6 :
ret = McNuggets(n-6)
return ret``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool check(vector<int>& s, int target)
{
if (target < 0)
return false;
if (target == 0)
return true;
bool ret = false;
for (int i = 0; i < s.size(); ++i)
{
ret = ret | check(s, target - s[i]);
}
return ret;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````## A solution for McNuggets problem on careercup (question?id=14974673)
##
##
validPacks = [20, 9, 6]
howmany = [0, 0, 0]

def McNuggets(n) :
""" Returns true or false, depending upon whether McNuggets for given
amount are possible. Additionally also gives the combination
"""
global howmany
for i in range(len(validPacks)):
curpack = validPacks[i]
if (n - curpack) >= 0:
retval = McNuggets(n-curpack)
howmany[i] += 1
if retval is True:
return retval
else:
howmany[i] -= 1

if n == 0:
return True

howmany = [0, 0, 0]
return False

for i in range(6,100):
howmany = [0, 0, 0]
print i, ":", McNuggets(i), howmany``````

Comment hidden because of low score. Click to expand.
0

Gosh -- this has screwed up indents!! Right indentation is left as an exercise!! ;-)

Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved by breaking down the problem to its sub problems. Given a number, take 6 out of it. Can the rest be be broken up between {9, 20}? (and recurse). If not possible, then take 2*6 out of the number. Can the rest be broken up between {9, 20}? and so on.

Here is the code.

``````bool nuggets (int n)
{
vector<int>  denoms;

denoms.push_back(6);
denoms.push_back(9);
denoms.push_back(20);

return isComboPossible(n, denoms);
}

bool isComboPossible (int n, vector<int>  denoms)
{

bool bPossible = false;
int  i;

if (n <= 0) {
return false;
}

for (i = 0; i < denoms.size(); ++i) {
int nHowMany = n / denoms[i];
bPossible = (n % denoms[i] == 0);

if (bPossible) {
cout << denoms[i] << " nuggets: " << nHowMany << endl;
return true;
}
}

if (denoms.size() == 1) {
return false;
}

int denom1 = denoms;
denoms.erase(denoms.begin());

for (i = 0; denom1 * i < n && !bPossible; ++i) {
bPossible = isComboPossible (n - denom1 * i, denoms);
}

if (bPossible) {
cout << denom1 << " nuggets: " << i - 1 << endl;
}

return bPossible;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Like someone mentioned below, its a coin change problem.

Code:

``````#include <iostream>

using namespace std;

int mcNuggets(int keys[], int key_size, int n)
{
if(key_size == 0)
return 0;

if(n == 0)
return 1;

int store[n+1];
for(int i = 1; i< n+1; i++)
store[i] = 0;
store = 1;

for(int i = 0; i<key_size; i++)
for(int j = 0 ; j < n+1; j++) {
if(j >= keys[i])
store[j] =  store[j] | store[j-keys[i]];
}

if(store[n] == 1)
return 1;

return 0;

}
int main(int argc, char **argv)
{
int keys[] = { 6, 9, 20};
int n;
cin >> n;
if(mcNuggets(keys, 3, n))
cout << "Possible" <<endl;
else
cout << "Not Possible" << endl;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a question from your midterm. Stop cheating!

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<stdlib.h>
using namespace std;

int count(int *arr,int n,int number)
{

if(number==0) return 1;
if(number<0) return 0;
if(n<=0 && number>=1) return 0;
return count(arr,n,number-arr[n-1])+count(arr,n-1,number);

}

int main()
{

int arr[] = {6,9,20};
int m = sizeof(arr)/sizeof(arr);
cout<< count(arr, m, 40);

return 0;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Not a good idea to use recursion. Evolve your solution to use DP,
Recurrence relation:
Ways(x)=Ways(x-6)+Ways(x-9)+Ways(x-20)

If Ways(n)>0 return true
else return false

Comment hidden because of low score. Click to expand.
0
of 0 vote

a*20 + b*9 + c*6
value of a b c can be decided as by linear probing - taking value of a b c in order of bits below:

000
001
010
011
101
110
111

if the number is greater, then re-place 1 with 2 3 and 4 ( so on).

We can also resort to binary search for getting the value of a b c.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Eh, a brute force solution.

``````# desired_num: desired number of mcnuggets
def get_mcnuggets(desired_num):
current_num = 0
a, b, c = [0, 0, 0]
while 20*c <= desired_num:
b = 0
while 9*b <= desired_num:
a = 0
while 6*a <= desired_num:
current_num = 6*a + 9*b + 20*c
if current_num == desired_num:
return True
a += 1
b += 1
c += 1
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

No one seems to have suggested the bottom-up approach of constructing a list of possible numbers until we either reach or exceed n. The list is {0} initially and gradually grows, such as {0, 6, 9, 12, 18, 20, 24, 27...}. In each iteration, we use 3 different indices to keep track of the numbers in the list to which we should add 6, 9 and 20 to. We then add their minimum to the list, and increment the relevant indices. We need to make sure we don't add numbers that are already in the list by checking that this minimum is actually greater than the maximum of the list.

``````static boolean possible2(int n) {
ArrayList<Integer> numbers = new ArrayList<Integer>();
int p6 = 0;
int p9 = 0;
int p20 = 0;
// compiler complains if we use while(true) here
for(int i=0; i<n; i++) {
int a = numbers.get(p6) + 6;
int b = numbers.get(p9) + 9;
int c = numbers.get(p20) + 20;
int min = min3(a, b, c);
if(min == n)
return true;
if(min > n)
return false;
if(min > numbers.get(numbers.size()-1))
if(a == min)
p6++;
if(b == min)
p9++;
if(c == min)
p20++;
}
return false;
}

static int min3(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean isTrue(int n){
if(n < 0)
return false;
if(n == 0)
return true;
return isTrue(n-6) || isTrue(n-9) || isTrue(n-20);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````<?php
function mc(\$nb) {
\$nb = \$nb % 180;
while (\$nb >= 0) {
if (\$nb % 3 == 0 && \$nb != 3) {
return true;
}
\$nb -= 20;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool mcNugget(int n)
{
static std::vector<int> notWorking = {1,2,3,4,5,7,8,10,11,13,14,16,17,10,22,23,25,28,31,34,37,43};

return notWorking.find(n) == notWorking.end();
}``````

LOL, seems as if all number above 43 can be composed by nuggets. So buy a lot and you can't be wrong... I verified it up to 2048 with brute force.

Comment hidden because of low score. Click to expand.
0
of 0 vote

For the concrete case, use a little number theory in advance of coding:

6-packs + 9-packs only -> 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, etc.
add a 20-pack -> 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, etc...
add two 20-packs -> 40, 46, 49, 52, 55, 58, etc.

Basically, if you want more than 60 nuggets, you can always get your exact nugget meal.

For values less than 60, just hard code a lookup table or use the recursive algorithm, which is efficient enough for small numbers despite exponential time.

The only unreachable numbers are 1,2,3,4,5,7,8,10,11,13,14,16,17,19, 22, 23, 25, 28, 31, 34, 37, and 43.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool
canCountmcNugget (int n) {
vector <bool> dp [n + 1];
fill (dp.begin (), dp.end (), false);
dp  = true;
for (int i = 1; i <= n; i++) {
if (i >= 6) dp [i] |= dp [i - 6];
if (i >= 9) dp [i] |= dp [i - 9];
if (i >= 15) dp [i] |= dp [i - 15];
}
return dp [n];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

function is_comb(\$n)
{
for (\$i=0;\$i<=(int)(\$n/20);\$i++)
{
\$x=\$n-\$i*20;
if (\$x%3==0 and \$x>=6) return true;
}
return false;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static boolean checkMcNuggets(int n){
if (n  >= 6 && n%3 == 0){
return true;
}
if (n >= 20 && n%3 == 2 && n != 23){
return true;
}
if (n > 40 && n%3 == 1 && n != 43){
return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

well, anything divisible by 3 and greater than 5 can be represented by 6&9,so i have the following python code... does it work?

``````def buyNug(n):
if n < 0:
return False
if n%20 == 0:
return True
if n>3 and n%3 == 0:
return True
if n<20:
return False
else:

Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem is the same as the ol' "minimum many quarters, dimes, nickels, and pennies do you need to make up x cents?" only quite a bit easier, because you don't need to keep track of a, b, c: you just need to determine if a, b, and c can exist such that their combination satisfies the conditional statement (6a + 9b + 20c == n)

And here it is in Python

``````def mcnuggets(n):

d = n
while d >= 20:
d = d - 20
while d >= 9:
d = d-9
while d >= 6:
d = d - 6
return d == 0

print mcnuggets(16)``````

Comment hidden because of low score. Click to expand.
0

It's also important to note that you can get it by taking the modulo of subsequently decreasing parts, as another answer here indicates (- Y):

``return ( ( ( n % 20 ) % 9 ) % 6 == 0 )``

But keep in mind that the code above is exactly what the hardware does in this case. It subtracts 20 until the number is below 20, then subtracts 9 from that number until that number is below 9, and then subtracts six from that number until that number is below 6. If the remaining number is 0, return True.

Not really important overall, but being able to mention both in an interview would definitely give you some nerd points xD

Comment hidden because of low score. Click to expand.
0

This doesn't work...
33 can be made of (3x9)+(1x6) - but fails in your example...

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(1) time complexity

``````bool integerDivide(int x,int &a,int &b,int &c)
{// 6a + 9b + 20c = x
//  0<= a < 9
// 0<= b < 20
//  0<= c
//==> 6*8 + 9*19 + 20c >= x
// ==> c>=(x-6*8-9*19)/20  &&  c>=0 && c <= x/20
if (x<0)
{
return false;
}
for (c=max((x - 6*8 -9*19)/20,0);c <= x/20;c++)
{//implement (6*8+19*9 )/ 20 times at most
int left_x = x - 20 * c;
for (a=0;a<9;a++)
{
for (b=0;b<20;b++)
{
if(left_x == 6*a + 9*b)
return true;
}
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean checkNuggets(int n) {
if (n == 6 || n == 9 || n == 20) return true;
if (n < 5) return false;

return checkNuggests(n - 6) || checkNuggests(n - 9) || checkNuggests(n - 20);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

def McNugget(x):
x=int(x)
a=x%20
if a != 0 :
b=a%9
if b != 0:
c=b%6
if c != 0 :
print "failed"
else:
print "Number of 6 Nuggets : ", b/6
print "Number of 9 Nuggets : ", a/9
print "Number of 20 Nuggets: ", x/20

Comment hidden because of low score. Click to expand.
0
of 0 vote

def McNuggets(n):
if n < 6:
return False
elif n%3 == 0 or n%20 == 0:
return True
i = 2
while 3*i < n:
if (n - 3*i)%20 == 0:
return True
i = i + 1
return False

Comment hidden because of low score. Click to expand.
0
of 0 vote

Two variations that run in O(1):

``````def McNuggets(n):
n %= 20
n %= 9
n %= 6
return n == 0``````

and

``````def McNuggets(n):
n %= 20
n %= 9
return n % 6 == 0``````

Comment hidden because of low score. Click to expand.
0

For those who like 1 liners:

``````def McNuggets(n):
return ((n % 20) % 9) % 6 == 0``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def getCombN(N):
if(N==0):
return True
if(N-20<0):
if(N-9<0):
if(N-6<0):
return False;
return (getCombN(N-6) or getCombN(N-9) or getCombN(N-20))

print(getCombN(15))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
*
* @author just_do_it
*
* Check if there exists positive integral solution to
* 6a + 9b + 20c = n
*
* you can assume n < 60
since for n>60, one of n-60, n-20 or n-40 is divisible by 3 and can be assembled from 6 and 9
*/
public class McDonaldPurchaseProblem {

/*static boolean solvable[] = new boolean;

static void precomputeSolvableNumbersLessThan60(){

}*/

static boolean solvable(int n){
if(n>=60) return true;
int m = n%60;
if(m == 0){
return true;
} else {
if(m %3 == 0){
if(m >=6){
return true;
}
} else if (m < 20){
return false;
}

if(m %20 == 0){
return true;
} else {
if(m>20 && (m-20) %3 == 0 && m-20 >= 6){
return true;
}
if(m>40 && (m-40) %3 == 0 && m-40 >= 6){
return true;
}
}
}

return false;
}

public static void main(String[] args){

for(int i = 1; i < 60; i++){
System.out.println(i + "\t" + solvable(i));
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def McNuggetscalc(n):
if ((n%6 == 0) or (n%9 == 0) or (((n%9)%6) == 0) or ((((n%20)%9)%6) == 0)):
return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This doesn't work for me --- any suggestions --- please see the python code below:

``````def is_nugget_number(num):
for i in range(10):
for j in range(10):
for k in range(10):
if(i==0 and j==0 and k==0):
continue
if (num%(i*6 + j*9 + k*20)==0):
return True
return False

def main():
nuggets=1

if (is_nugget_number(nuggets)):
else:

nuggets+=1

Comment hidden because of low score. Click to expand.
0
of 0 vote

def McNuggets(n):
if n == 0:
return True
elif n < 0:
return False
else:
return n >= 0 and (McNuggets(n-6) or McNuggets(n-9) or McNuggets(n-20))

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is to recursively calculate the combinations and return true when you find a solution, false if you are exhaustive.

{
//6a+9b+20c=n
if (n < 0) return false;
if (n == 0) return true;
if (canbuyChickenNugget(n - 6)) return true;
if (canbuyChickenNugget(n - 9)) return true;
if (canbuyChickenNugget(n - 20)) return true;
return false;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is to recursively calculate the combinations and return true when you find a solution, false if you are exhaustive.

``````static bool canbuyChickenNugget(int n)
{
//6a+9b+20c=n
if (n < 0) return false;
if (n == 0) return true;
if (canbuyChickenNugget(n - 6)) return true;
if (canbuyChickenNugget(n - 9)) return true;
if (canbuyChickenNugget(n - 20)) return true;
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here you have a Python implementation of the solution using DP. As a lot of people said, this is very similar to the Coin Change Problem

``````PACKAGES = [6,9,20]

def mc_nuggets(packages, n):
# partial_solutions[i] is True if exists a possible combination of packages for i
partial_solutions = [True]
for i in range(1, n + 1):
partial_solutions.append(any([partial_solutions[i - p] if (i - p) >= 0 else False for p in packages]))
#print "Partial:", list(enumerate(partial_solutions))
return partial_solutions[n]

assert mc_nuggets(PACKAGES,1) == False
assert mc_nuggets(PACKAGES,5) == False
assert mc_nuggets(PACKAGES,6) == True
assert mc_nuggets(PACKAGES,9) == True
assert mc_nuggets(PACKAGES,12) == True
assert mc_nuggets(PACKAGES,10) == False
assert mc_nuggets(PACKAGES,16) == False
assert mc_nuggets(PACKAGES,20) == True
assert mc_nuggets(PACKAGES,29) == True
assert mc_nuggets(PACKAGES,26) == True
assert mc_nuggets(PACKAGES,27) == True``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def nuggets(n):
q=0
r=0
d={}
d=0
d=0
d=0
if n>=20:
d=n/20
n=n%20

if n>=9:
d=n/9
n=n%9

if n>=6:
d=n/6
n=n%6
if n==0:
return d
else:
return "Not possible to pack"``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def nuggets(n):
q=0
r=0
d={}
d=0
d=0
d=0
if n>=20:
d=n/20
n=n%20

if n>=9:
d=n/9
n=n%9

if n>=6:
d=n/6
n=n%6
if n==0:
return d
else:
return "Not possible to pack"``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I tried the following,

``````def McNuggets(numb):
if numb % 6 == 0 or numb % 9 == 0 or numb % 20 == 0 or numb % 15 == 0 or numb % 26 == 0 or numb % 29 == 0:
print True
else:
print False``````

I am getting the correct result, please tell me if otherwise

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have coded as follows:

``````def McNuggets(numb):
if numb % 6 == 0 or numb % 9 == 0 or numb % 20 == 0 or numb % 15 == 0 or numb % 26 == 0 or numb % 29 == 0:
print True
else:
print False``````

I am getting the correct result, please tell me if otherwise

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have coded as follows:

``````def McNuggets(numb):
if numb % 6 == 0 or numb % 9 == 0 or numb % 20 == 0 or numb % 15 == 0 or numb % 26 == 0 or numb % 29 == 0:
print True
else:
print False``````

I am getting the correct result, please tell me if otherwise

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````# Python
def mcN(n):
m=n%20%9%6
if (m == 0):
else:

# Test
for i in range(1,100):
mcN(i)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my solution, not sure I'd come up with it under pressure. The hard part was coming up with the list of factors:
6
9
20
15
26
29
35
Not sure it's all that efficient either. The positive thing is that it uses a generator, so the value is yielded, though it's only 7 values.

``````from itertools import chain, combinations
from functools import reduce
def McNuggets(n):
sizes = [6,9,20]  # portion sizes. Any combination of these factored will give you a valid portion size.
g = (subset for subset in chain(*map(lambda x: combinations(sizes, x), range(1, len(sizes)+1))))
for i in g:
f = reduce(lambda x,y: x + y , i)
if n%f == 0:
return True
return False``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````McNuggets ( n ) {
if ( n % 6  == 0 ) return true;

if ( ( n % 9 ) % 6 == 0 ) return true;

if ( ( ( n % 20 ) % 9 ) % 6 == 0 ) return true;

return false;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````bool Check(int n)
{
n = n%20;
return n == 0 || n == 6 || n ==9 || n == 12 || n == 18;
}``````

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
-2
of 2 vote

boolean McNuggets(int n)
{

int packages[] = {20, 9, 6};

for (int i = 0; i < 3; i++) {
n %= packages[i];

if (0 == n)
return true;
}

return false;
}

Comment hidden because of low score. Click to expand.
0

n=24(4*6), Your code will return false.
The earlier recursive solution would work though.
@nitingupta180 it works for n=55;

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.