CareerCup

simple and easy

bool isPossible(int N)
{
    while(N > 0)
        if(N == 0 || ((N % 3 == 0) && N >= 6))
            return true;
        else N -= 17;
    return false;
}

Simple code with brutal

bool recursive(int n)
{
	if(n == 0) return true;
	else if(n < 0) return false;
	else return recursive(n-6) || recursive(n-9) || recursive(n-17);
}

Coin Change problem can be done in O(NM) where M is the number of different packet. The bruceforce is more than O(2^M).

public int[][] coinchange(int[] coin, int key){
     int[][] CH = new int[key+1][];
     for(int i=0;i<CH.length;i++){
	CH[i] = new int[coin.length+1];
     }
		
     //base case when CH[0][] = 0    // can do
     //base case when CH[>0][>0] = -1 // can't do
     for(int i=0;i<key+1;i++){
	for(int j=0;j<coin.length+1;j++){
		CH[i][j] = (i==0?0:-1);
	}
     }// initialize
		
     //CH[i][j] = CH[i][j-1] if coin[j] not chosen   a)
     //           CH[i-coin[j]][j] if coin[j] chosen b)
     for(int i=1;i<key+1;i++){
	for(int j=1;j<coin.length+1;j++){
		int temp = -1;
	//check validity of case b)
	if(coin[j-1] <= i)
		temp = CH[(i - coin[j-1])][j];
	CH[i][j] = (temp>CH[i][j-1]?temp:CH[i][j-1]);
		}//endfor
	}//endfor
	return CH;
	}

public static boolean isPossible(int num){
		for(int i=0;i<=num/6;++i){
			for(int j=0;num>=6*i+9*j;++j){
				if((num-6*i-9*j)%17==0)return true;
			}
		}
		return false;
	}

Following should be O(N) where N is the total number that we want to check for. We can use DP here to make sure that we don't traverse the same values again.

public boolean packets(List pckt, int currentVal, int reqVal, HashMap check){
	Iterator itr = pckt.iterator();
	while(itr.hasNext()){
		int val = (Integer)(itr.next()).intValue();
		if(currentVal + val == reqVal)
			return true;
		else{
			if(!(check.contains(currentVal + val)) && currentVal + val < reqVal){
				check.add(currentVal + val);
				if(packets(pckt,currentVal + val,reqVal,check))
				return true;
			}
		}
         }
	return false;
}

<pre lang="" line="1" title="CodeMonkey31942" class="run-this">This is 0-1 Knapsack problem and can be solved in O(NM) time and O(N) space where N is the target value and M are the number of packets.

bool IsPossible(int* packets, int num_packets, int target)
{
bool* possible = new bool[target + 1];
possible[0] = true;
for (int i = 1 ; i <= target ; i++) {
possible[i] = false;
for (int j = 0 ; j < num_packets ; j++) {
if (packets[j] > i) continue;
if (possible[i - packests[j]]) {
possible[i] = true;
break;
}
}
}
bool val = possible[target];
delete[] possible;
return val;
}

</pre><pre title="CodeMonkey31942" input="yes">
</pre>

if N%17%9%6 == 0
return true;
else return false;

1) Any number divisible by 6 or 9 -> should be divisible by 3
i.e. if a number is divisible by 3 and is greater then 6 -> then blindly it's possible.
For example -> 6,9,12(6+6),15(9+6),18(9+9),21(6+6+9) etc ...

2)17 is a prime number , so we can devide the number by 17 , get the reminder , check if greater then equal to 6 and divisible by 3 .. :)

so code can be like
Check(int number)
{
if(number >= 6 && number mod 3 == 0) return true;
int reminder = number mod 17 ;
if(reminder >=6 && reminder mod 3 ==0) return true;
return false;
}

I do not remember old school logic of finding all possible sums for an expression of form:

ax+by+cz=n

here a , b , c and n are known and equals 6,9,17 and 29.
If total number of ways comes out to be zero than it is not possible or it is possible.


Now I remember a little bit of logic which returns back to some computational formula:

like total number of ways of forming sum of 29 is factor of 29 in following expression:

(1+x^6+x^12.........)*(1+x^9+x^18..)*(1+x^17+x^34.......)

Now based on applying GP it returns to finding coefficient of x^29 in ((1-x^6)*(1-x^9)*(1-x^17))^-1 .


Can this be used to solve this problem.
I do not know how to proceed further from this point.
Still searching for that old high school algebra book in which this article is present.

First of all as mentioned above if a number is divisible by 3 and not divisible by 6 than it can be written in the form of 1*9 + x*6 where x is an integer and if it is divisible by 6 than no need to worry :) .

Suppose there is a number N ,
1. Divide N by 17 and lets say remainder is r
2. r can be anything from 1 to 16
3. we just need to find out that by adding 17 to r can we write that number in the multiples of 6 and 9 (through above method)
if not then add 17 to the number again and then check again
4. keep adding untill the number would become greater than N. If the number has become greater than N then it is not possible to write it into multiples of 17,6 and 9.


e.g1 N = 125
k = N%17 = 5
5 not possible to write it in multiples of 6 and 9
5+17 =22 again not possible
but for 39 it is possible.
Ans is True

e.g2
Let N is 28
28%17 = 11
not possible
so 11+ 17 = 28 again not possible
hen 28+17=45 number has become greater than N
ans is False

if(N%17%9%6 == 0 || N%17%9 ==0 || N%17%6 ==0 || N%9%6 ==0 || N%17 ==0 || N%9 == 0 || N%6 ==0 )
{ return true ;}
else { return false ; }

First find all possible combination of 6 , 9 and 17. Ie 6, 9, 17, (6+9), (9+17), (6+17), (6+9+17). Any number having N% any of the above as 0 is true else false.

Wait, isn't it always possible (by the Chinese theorem)?

Now the problem is that we cannot sell negative amount of boxes, and thus it is not always possible. However, it is certainly possible for anything above lcm(6,9,17)=2*3*3*17=306

If ((n mod(17))mod(9))mod(6) == 0

for(i=0;i<6;i++)
for(j=0;j<9;j++)
for(k=0;k<17;k++)
if( 6*i + 9*j +17*k == n )
you can buy.
else{
cant
}

n[-17] -> n[-1] = false;
n[0] = true;
for (int i = 1; i <= N; i++)
{
n[i] := n[i - 6] || n[i - 9] || n[i - 17];
}

then n[N] is the result

int canbuy(int ps[ ], int cost)
{
if(cost == 0)
return 1;
if(cost < 0)
return 0;

for(int i=0; i<3; i++)
if(canbuy(ps, cost-ps[i]))
return 1;

return 0;

private boolean canBuy(int data){
int [] A = {17,9,6};
int temp = data;

if(temp<A[2]) return false;

if(data < A[0]){
if(temp<A[0] && temp>A[1]) temp = temp % A[1];
else if(temp<A[1]&& temp>A[0]) temp = temp%A[0];
else if(temp<A[0]&& temp>A[2])temp = temp%A[2];
if(temp==0)return true;
}
if(data ==A[0]|| data==A[1]|| data ==A[2])
return true;

while(temp >0){
if(temp>A[0]) temp = temp% A[0];
else if(temp<A[0] && temp>A[1]) temp = temp %A[1];
else if(temp<A[1]&& temp>A[2]) temp = temp%A[2];

if(temp==0 || temp ==A[1] || temp ==A[2]) return true;
else if(temp<A[2])return false;
}

return false;

}

It shows that if N>=40, it will always return true.
40 = 17 + 17 + 6
41 = 17 + 6 + 6 + 6 + 6
42 = 6*7
43 = 17 + 17 + 9
44 = 17 + 9 + 9 + 9
45 = 5 * 9

therefor, for f(46) = 6 + f(40)
f(47) = 6+f(41)
..
and so on...

static bool IsPossible(int num)
{
bool bValue = false;
if (num < 6)
bValue = false;
else if (((num % 17) % 9) % 6 == 0)
bValue = true;
else if (((num % 9) % 6 ) == 0)
bValue = true;
else if (num % 6== 0)
bValue = true;
return bValue;
}

Below is the efficient code, based on the observation, that any number divisible by 3 (except for 3) can be bought as a combination of 6*x + 9*y, and 17=3*5+2, and 34=17*2=3*11+1, which provide access to numbers not divisible by 3, as long as they are not less than 17 and 34 respectively:

switch (num % 3) {
case 0: return num >= 6;
case 1: return num == 34 || num >= 40;
case 2: return num == 17 || num >= 23;
}