CareerCup

Here we have a restriction that makes this not NP-complete: namely, that we consider only coin combinations of 3 coins or smaller. If we considered D coins, there is a simple O(N^(D-1)) algorithm, so here there will be an O(N^2) algo.

Add all the coins to a set. Ask the set whether there's a single coin that will work. If yes, return true. If not, iterate through the set, taking each value and checking if the value that would have to be added to that value is also in the set. If that's ever so, return true. If not, to check for combos of three, try each combo of 2 (O(N^2)) and check if the value that must be the remaining value is in the set. Overall complexity is O(N^2).

Can some one write a code fort this program. I am learning and need some help.

Yes, it is a knapsack problem with additional constraints

{
public void GetCoins(int totalPrice, int noOfCoins, int denominations[])
{
int coinLimit = 3;
int in[] = new int[coinLimit];
for(int i = 0; i < coinLimit; i++)
in[i] = 0;
boolean exists = Coins(totalPrice, noOfCoins, denominations, in);
if(exists)
for(int i = 0; i < coinLimit; i++)
System.out.print(in[i]);
else
System.out.print("-9999");
System.out.println();
}
public boolean Coins(int totalPrice, int noOfCoins, int denominations[], int taken[])
{
if(noOfCoins >= 3 && totalPrice != 0)
return false;
if(totalPrice == 0)
return true;
for(int i = 0; i < denominations.length; i++)
{
if(noOfCoins > 1)
{
if(totalPrice - denominations[i] >= 0 && taken[noOfCoins - 1] <= denominations[i])
{
taken[noOfCoins] = denominations[i];
boolean flag = Coins(totalPrice - denominations[i], noOfCoins + 1, denominations, taken);
if(flag)
return true;
taken[noOfCoins] = 0;
}
}
else
{
if(totalPrice - denominations[i] >= 0)
{
taken[noOfCoins] = denominations[i];
boolean flag = Coins(totalPrice - denominations[i], noOfCoins + 1, denominations, taken);
if(flag)
return true;
taken[noOfCoins] = 0;
}
}
}
return false;
}
}
Above code works fine but the complexity is not good. Complexity is exponential

public void GetCoins(int totalPrice, int noOfCoins, int denominations[])
{
int coinLimit = 3;
int in[] = new int[coinLimit];
for(int i = 0; i < coinLimit; i++)
in[i] = 0;
boolean exists = Coins(totalPrice, noOfCoins, denominations, in);
if(exists)
for(int i = 0; i < coinLimit; i++)
System.out.print(in[i]);
else
System.out.print("-9999");
System.out.println();
}
public boolean Coins(int totalPrice, int noOfCoins, int denominations[], int taken[])
{
if(noOfCoins >= 3 && totalPrice != 0)
return false;
if(totalPrice == 0)
return true;
for(int i = 0; i < denominations.length; i++)
{
if(noOfCoins > 1)
{
if(totalPrice - denominations[i] >= 0 && taken[noOfCoins - 1] <= denominations[i])
{
taken[noOfCoins] = denominations[i];
boolean flag = Coins(totalPrice - denominations[i], noOfCoins + 1, denominations, taken);
if(flag)
return true;
taken[noOfCoins] = 0;
}
}
else
{
if(totalPrice - denominations[i] >= 0)
{
taken[noOfCoins] = denominations[i];
boolean flag = Coins(totalPrice - denominations[i], noOfCoins + 1, denominations, taken);
if(flag)
return true;
taken[noOfCoins] = 0;
}
}
}
return false;
}
Above code works fine but the complexity is not good. Complexity is exponential

A simple and recursive program, works very well but complexity is ok

class coins
    {
        public int? GetCoins(int total, int totalcoins, int[] denominations)
        {
            if (total > 0 && totalcoins >= 0 && denominations!=null)
            {
                for (int i = 0; i < denominations.Length; i++)
                {
                    if (denominations[i] == total)
                    {
                        System.Console.WriteLine(denominations[i]);
                        return denominations[i];
                    }
                    else if (denominations[i] > total)
                    {
                        continue;
                    }
                    else if (denominations[i] < total)
                    {
                        if (denominations[i] + GetCoins(total - denominations[i], totalcoins - 1, createnewarray(denominations)) == total)
                        {
                            System.Console.WriteLine(denominations[i]);
                            return denominations[i];
                        }
                    }
                }
            }
            return null;
        }

        public int[] createnewarray(int[] denominations)
        {
            int[] newdeno = new int[denominations.Length - 1];            
            for (int i = 1; i < denominations.Length; i++)
            {
                newdeno[i - 1] = denominations[i];
            }
            return newdeno;    
        }
    }

This problem can be broken into:
finding if a single element is equal to sum. (easily solvable)
finding if 2 elements are equal to sum. (solution easily available)
finding if 3 elements are equal to sum. (slightly harder than 2 but again commonly known).

Here is the code that does all 3 using 2 loop. The complexity in worst case is n^2. It assumes a sorted input array & stops at the first solution.

The output for the current problem is 10, 40, 50.

void GetSumIn3ElementsOrLess(int* arr, int length, int sum)
{
	int start, end, newsum;
	bool success = false;

	// Iterate from first element to the last one.
	for (int index = 0; index < length && success == false; index++) {

		// If the current element is the sum, we have solution. break!
		if (arr[index] == sum) {
			cout<<"\nSolution at index: "<<index<<" Value:"<<arr[index];
			success = true;
			break;
		}

		start = 0;
		end = length -1;

		while (start < end) {
			// If the current element + first pointer equal sum, we have solution. break!
			if (arr[index] + arr[start] == sum) {
				cout<<"\nSolution at index: "<<index<<" & "<<start<<" Values:"<<arr[index]<<" & "<<arr[start];
				success = true;
				break;
			}
			// If the current element + last pointer equal sum, we have solution. break!
			if (arr[index] + arr[end] == sum) {
				cout<<"\nSolution at index: "<<index<<" & "<<end<<" Values:"<<arr[index]<<" & "<<arr[end];
				success = true;
				break;
			}

			newsum = arr[index] + arr[start] + arr[end];
			// If the current element + first + last pointer equal sum, we have solution. break!
			if (newsum == sum) {
				cout<<"\nSolution at index: "<<index<<" & "<<start<<" & "<<end
					<<" Values:"<<arr[index]<<" & "<<arr[start]<<" & "<<arr[end];
				success = true;
				break;
			}
			// If the current sum is less, move the start pointer forward to get a larger value.
			else if (newsum < sum) {
				start++;
			}
			// If the current sum is higher, move the end pointer back to get a smaller value.
			else {
				end--;
			}
		}
	}
	if (!success) {
		cout<<"\nNo solution possible";
	}
}

void GetSumIn3ElementsOrLessTest()
{
	int arr[] = {10,30,40,50,70};
	int length = sizeof(arr)/sizeof(arr[0]);
	int sum = 100;

	GetSumIn3ElementsOrLess(arr, length, sum);
}

void get(int tp,int no,int deno[])
{
int op[tp+1];
int coin[tp+1];
int min;
int i,j;
int opt[3];
op[0]=0;
int c=0;
for(j=1;j<=tp;j++)
{
min =999;
for(i=0;i<=no;i++)
{
if(deno[i] <= j)
{
if((1+op[j-deno[i]]) < min)
{
min = 1+op[j-deno[i]];
c=deno[i];
}
}
}
op[j] =min;
coin[j]=c;
}
int ans[3];

if(op[tp] <=3)
{
int a=tp;
while(a!=0)
{
printf(" %d ",coin[tp]);
a=a-coin[tp];
tp = tp-coin[tp];
}
}
}

The interviewer is just tricking us.
All we have to check is if the sum or 1 or 2 or 3 numbers in an array sum to the given number which can be done in O(n)+O(nlogn)+O(n^2) which is )(n^2)