CareerCup

change(n)= 1+ min({change(n-1),change(n-2),change(n-5)})
where 1,2,5 are sample denominations..

Standard DP solution for this problem...

int sum  = 11; // the change sum you want
    vector<int> value;
    value.push_back(1),value.push_back(3),value.push_back(5); // for testing purpose vector of denominators
    vector<int> minCoinsForSum(sum+1,INT_MAX); //state Array for DP
    minCoinsForSum[0] = 0;
    for(int i = 1;i<=sum; ++i)
        for(int j = 0;j<(int)value.size() ;++j)
            if(value[j]<=i && (minCoinsForSum[i-value[j]]+1) < minCoinsForSum[i])
                minCoinsForSum[i] = minCoinsForSum[i - value[j]] + 1;

    for(int i=0; i <(int)minCoinsForSum.size(); i++)
        cout<<minCoinsForSum[i]<<endl;

    return 0;

public string ReturnMinChange(int cents)
{
// Let's say I have 25, 10, 5, and 1 cetns to give
string giveReturn = string.Empty;
int[] centsArr = new int[] { 25, 10, 5, 1};
foreach (int i in centsArr)
{
if (cents >= i)
{
giveReturn += (cents / i) + " " + i + " cents, ";
cents = cents % i;
if (cents == 0) break;
}
}
return giveReturn;
}

The question is not clear to me :(

This shud work..................
{
void main()
{
cout<<"Hello World!"<<endl;
int coins[3] = {20, 15, 1};
int val = 31;
int rem = 0;
int i = 0;
int num = 0;
while ( 1 )
{
num = val / coins[i];
rem = val % coins[i];
if(!rem)
break;

cout << num << " coins required of denomination " << coins[i] << endl;
i++;
val = rem;
}
cout << num << " coins required of denomination " << coins[i] << endl;
}
}

Agreed .. but if u look closely, both r the same... only variables names are different

I guess the first solution doesn't have variables. It just gives the correct recurrent function :-)

AA is totally wrong, he obviously didn't even run his code.

linear programing solves this easily, but I will think about it for a second.

is the question:
if i have multiple 25, 10, 5, and 1 cents.
and lets say i want to give some number of change to someone.
find the algo to provide the change with minimum coins.

that means, if change number is 55, i should give (2)25 cents, and (1)5 cents. Instead of (11)5 cents or (55)1 cents.

Spiderman, please clarify this

try running the code , then comment

int main()
{
int coins[4] = { 25,10,5,1};
int amount;
int i;
int numCoins;

cout<<"\n Enter the amount";
cin>>amount;
for(i=0;i<4;i++)
{
numCoins = amount/coins[i];
amount = amount - numCoins*coins[i];
cout<<"\n required "<<numCoins<<" of denominaion "<<coins[i];

if(amount == 0)
break;
}
return 0;
}
hope this should help.

this can be solved using dp..
let C[p] represent the min no of coins needed for getting amount p
let d is the array of denominators(size k)
then we can write the recurrence as follows:

C[p]=0 if p=0
= min(1 + C[p-d[i]]) here d[i]<=p and 1<=i<=k

then just calculate the array C[] in bottom up fashion
time complexity: O(nk)

public class MinimumChange {
public static HashMap<Integer,Integer> minimumChange(int [] a ,int k,int amount){
if(k > 0){
int temp=amount;
int remainingAmount=1000;
int denominationCount;
HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
for(int i=k;i>=0;i--){
if(remainingAmount <= 0){
break;
}
denominationCount=temp/a[i];
temp=temp%a[i];
remainingAmount=temp;
map.put(a[i], denominationCount);
}
if(remainingAmount==0){
return map;
}
else{
return minimumChange(a,k-1,amount);
}
}
return null;
}
public static void main(String[] args) {
int [] a ={3,4,5};
int len=a.length;
HashMap<Integer, Integer> map=minimumChange(a,len-1,12);
System.out.println(map);
}

}

Is this algorithm correct?

{
// CoinDenomination.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<Windows.h>
#include<atlstr.h>
typedef struct _deno
{
	CString individualDeno;
	CString denominations;
	int cnt;
	_deno()
	{
		individualDeno = _T("");
		denominations = _T("");
		cnt = -1;
	}
}Deno;
int getMin(int n,int *denom,int denomcnt,int currentNum,Deno *denomidations)
{
	
	int min = n + 1;
	int cnt = -1;
	for(int i=0;i<denomcnt;i++)
	{
		if(denom[i] <= currentNum)
		{
			int x = currentNum % denom[i];
			int y = currentNum/denom[i];
			if(!x)
			{
				cnt = denomidations[denom[i]].cnt * y;
				if(cnt < min)
				{
					min = cnt;
				}
			}
			else
			{
				if((denomidations[x].cnt != -1) || (denomidations[x].cnt != -2))
				{
					cnt = denomidations[denom[i]].cnt * y + denomidations[x].cnt;
					if(cnt < min)
					{
						min = cnt;
					}
				}
			}
		}
	}
	denomidations[currentNum].cnt = min;

	return min;

}
int FunmindenomCnt(int n,int *denom,int denomcnt)
{
	Deno *denominations = new Deno[n];
	int minDenom;
	for(int i=0;i<denomcnt;i++)
	{
		denominations[denom[i]].cnt = 1;
	}
	for(int i=0;i<=n;i++)
	{
		if(i >= denom[0])
		{
			if(denominations[i].cnt != 1)
			{
				minDenom = getMin(denominations[i-1].cnt,denom,denomcnt,i,denominations);
				denominations[i].cnt = minDenom;
			}
		}
		else
		{
			denominations[i].cnt = -2;
		}
			
	}
	return minDenom;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[3]={1,2,4};
	int mindenomCnt = FunmindenomCnt(7,arr,3);
	return 0;
}

}

private static int[] MergeArrays(int[] a, int[] b) {
		if(b==null)
			return a;
		int m = 19;  // number of elements in a
		int n = 9; // number of elements in b
		int x;
		while(m>=0 || n>=0){
			x=m+n+1;
			if(a[m]>b[n]){
				a[x] = a[m];
				a[m]=-1; m--;
			}else{
				a[x] = b[n];
				n--;
			}
			
			if(m<0){
				while(n>=0){
					a[n]=b[n];
					n--;
				}
			}
			if(n<0){
				break;
			}
		}
		
		return a;
		
	}

swetha reddy parava

sorry, posted code for some other question!!

swetha reddy parava