CareerCup

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

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

Oneliner in C:

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

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

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

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.

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

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

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

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

#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;
}

Can anyone give me this same code in Python ??

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

## 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

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

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;

}

This is a question from your midterm. Stop cheating!

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

}

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

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.

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

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

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

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

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.

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.

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];
}

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

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

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)

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)

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

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

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

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

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

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

/**
 * 
 * @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));
		   }
	   }

}

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

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

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

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

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

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

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"

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"

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

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

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

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

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

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

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

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