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[0]:
		possibleMcNuggets[0] = 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

- Alva0930 June 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- lolcoder January 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

btw, killer thinking.

- lolcoder January 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- quizzer January 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Zero2 February 15, 2014 | Flag
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));
    }
}

- Anonymous November 03, 2012 | Flag Reply
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

- Thank November 03, 2012 | Flag
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

- Anonymous November 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Neat solution!

- Jason Tu November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

But what if you want 39?

- A November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

elegant code but horrible space complexity

- Anonymous February 05, 2013 | Flag
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!

- Zero2 February 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Safi December 03, 2014 | Flag
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));
}

- gaspard01 February 11, 2013 | Flag Reply
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;
}

- Vinod November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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)

- Nitin Gupta November 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anish[1] November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nitin Gupta November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nitin Gupta November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- aka November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nitin Gupta November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);

- anish[1] November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- dingxwsimon November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sourav January 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sourav: read more

- anish January 18, 2013 | Flag
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)...??

- Divya November 03, 2012 | Flag Reply
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.

- Nitin Gupta November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- systck November 04, 2012 | Flag
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))

- Chad Parry November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- Anon November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Clever but unmaintainable code.

- gabhijit November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Chad Parry November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sebastian G. November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anish[1] November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anish[1] November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nitin Gupta November 05, 2012 | Flag
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

- Epic_coder November 07, 2012 | Flag Reply
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

- wick3dsunny November 13, 2012 | Flag Reply
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.
"""
# Your Code Here
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

- thank you November 03, 2012 | Flag Reply
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;
}

- Gaurav November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anyone give me this same code in Python ??

- Anonymous November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sathiyamoorthy January 26, 2014 | Flag
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;
}

- david November 04, 2012 | Flag Reply
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

- gabhijit November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gabhijit November 04, 2012 | Flag
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[0];
    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;
}

- nd November 04, 2012 | Flag Reply
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[0] = 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;

}

- systck November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a question from your midterm. Stop cheating!

- anon November 04, 2012 | Flag Reply
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[0]);
    cout<< count(arr, m, 40);

    return 0;

}

- Ritesh November 05, 2012 | Flag Reply
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

- Epic_coder November 07, 2012 | Flag Reply
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.

- PV November 07, 2012 | Flag Reply
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

- Jason Tu November 18, 2012 | Flag Reply
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>();
	numbers.add(0);
	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))
			numbers.add(min);
		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));
}

- Sunny December 18, 2012 | Flag Reply
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);
}

- li January 21, 2013 | Flag Reply
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;
}

- pinouchon February 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about:

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.

- FBNerd February 26, 2013 | Flag Reply
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.

- showell30@yahoo.com February 27, 2013 | Flag Reply
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 [0] = 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];
}

- wolfwood March 23, 2013 | Flag Reply
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;
}

- M March 27, 2013 | Flag Reply
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;
}

- cengin May 16, 2013 | Flag Reply
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:
		return buyNug(n-20)

- bugbag May 29, 2013 | Flag Reply
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)

- DevonMeyer212 September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- DevonMeyer212 September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- MickyD September 28, 2014 | Flag
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;
}

- linlookfor September 06, 2013 | Flag Reply
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);
}

- Simple solution using recursion. October 07, 2013 | Flag Reply
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

- ropo December 09, 2013 | Flag Reply
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

- charlie December 19, 2013 | Flag Reply
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

- Coltin March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For those who like 1 liners:

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

- Anonymous March 20, 2014 | Flag
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))

- Anonymous June 27, 2014 | Flag Reply
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[60];
	
	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));
		   }
	   }

}

- just_do_it July 27, 2014 | Flag Reply
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

- Satya September 05, 2014 | Flag Reply
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
    canbuy=0
    cantbuy=0

    while(canbuy-cantbuy<6):
        
        if (is_nugget_number(nuggets)):
            canbuy = nuggets
            print("canbuy: " + str(canbuy)) 
        else:
            cantbuy = nuggets
            
        nuggets+=1
            
    print("The highest number one can't buy =" + str(cantbuy))

- charl January 25, 2015 | Flag Reply
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))

- Anonymous February 08, 2015 | Flag Reply
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;
}

- Krish May 27, 2015 | Flag Reply
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;
        }

- Krish May 27, 2015 | Flag Reply
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

- pablodmusumeci June 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def nuggets(n):
    q=0
    r=0
    d={}
    d[6]=0
    d[20]=0
    d[9]=0
    if n>=20:
        d[20]=n/20
        n=n%20
        
    if n>=9:
        d[9]=n/9
        n=n%9
        
    if n>=6:
        d[6]=n/6
        n=n%6
    if n==0:
        return d
    else:
        return "Not possible to pack"

- Python Solution November 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def nuggets(n):
    q=0
    r=0
    d={}
    d[6]=0
    d[20]=0
    d[9]=0
    if n>=20:
        d[20]=n/20
        n=n%20
        
    if n>=9:
        d[9]=n/9
        n=n%9
        
    if n>=6:
        d[6]=n/6
        n=n%6
    if n==0:
        return d
    else:
        return "Not possible to pack"

- Python Solution November 24, 2015 | Flag Reply
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

- sonal December 19, 2015 | Flag Reply
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

- sonal December 19, 2015 | Flag Reply
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

- sonal khare December 19, 2015 | Flag Reply
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):
        print('Can buy '+ str(n))
    else:
        print('Can\'t buy ' + str(n))
        
# Test
for i in range(1,100):
    mcN(i)

- JKJ July 18, 2016 | Flag Reply
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

- John Markham April 24, 2020 | Flag Reply
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;
}

- Y November 12, 2012 | Flag Reply
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;
}

- Anonymous February 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about 15 ?

- pinouchon February 27, 2013 | Flag
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;
}

- Vinod November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aj__ November 05, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More