Delivered instantly as a PDF via email. For Software Engineers & SDETs
150 programming interview questions and answers
5 proven approaches to crack algorithm questions
10 mistakes candidates make, and how to avoid them.
How to prepare for technical and behavioral questions without wasting your time!
"The BEST book for acing your interview. It helped me land my Microsoft job, and it was worth every penny!" - Ravi (Accepted at Microsoft, Amazon and Facebook)
30 Day Money Back Guarantee: Don't love the book? We'll give you your money back!More Info
Saturday, April 24, 2010
Denominations of coins
You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
Actually the correct answer is 5 11 + 11 + 11 + 11 + 4
Solve with dynamic programming. I have used an arbitrary limit of 500 and allocated unneccesary space. Optimize it.
static uint MinCount(uint number) { int a = 4; int b = 7; int c = 11;
if (number > 500) return 0xffffffff;
uint[] array = new uint[501];
for (int i = 1; i <= number; i++) { if (i == a || i == b || i == c) { array[i] = 1; continue; }
uint min = 0xffffffff; if (i - a > 0) { if (min > array[i - a]) min = array[i-a]; } if (i - b > 0) { if (min > array[i - b]) min = array[i - b]; } if (i - c > 0) { if (min > array[i - c]) min = array[i - c]; }
The denom input is not specified.The code may not work for all inputs also. However in this case if the denom = {11,7,4} then it will be optimal solution. 4*11 + 1*4 = 5 coins
The algo is not complete. If u see, the 1st value in denom always makes for more number of coins, then the second(zero or more)... Wat happens in case of amount = 40 ? I think ans will be 10*4 which is not optimal.
The above algorithm is incorrect.. Lets take an example as amount to be 34 and denomination as just [10,8] According to above algorithm it will give value as 10+10+10 and then it will say We dont have enough denominations. Where as ideally it should be 10+8+8+8.
None of these are the solutions. Its a recursive algorithm. The problem with any of the algo's that "Take as many of the biggest denomination" is that they can break the mathematics when using strange denomenations.
ex: denom = {5,10,13,20} amount = 35; Most of the above mentioned algo's would try 35 - 20x1= 15 15 - 13x1 = 2; BROKEN!!!
Here's my solution
int Algo2(int * denom, int n1, int amount) { if(amount == 0 ) { return 0; }
int min = -1; for(int i=0; i< n1; i++) { if(amount < denom[i]) continue;
int numCoin = Algo2(denom,n1,amount - denom[i]) +1 ;
if(numCoin == 0) continue;
if(numCoin < min || min == -1) { min = numCoin; } }
The above algorithm is not an efficient and smart algorithm. For example if the amount is 120 and the denominations is {2,4,6}. It will a lot of time to compute the minimum denominations.
This is wrong. try for inputs {10,9,1} and find minimum coins for 153. The algorithm returns 18 coins however 153 can be obtained using only 17 coins (9*17=153)
void Min(int Sum[], int V, int curr); int main() { int V[10]; int n, Sum[20]; int S=0; cout<<"Enter the number of coins\n"; cin>>n; for(int i=0; i>V[i]; cout<<"\n"; } cout<<"Enter the Sum\n"; cin>>S;
for(int k=0;k<20;k++) { Sum[k]=10000; }
Sum[0]=0; for(int i = 0; i=0) { if(curr==0) { Sum[curr]=0; } else { if((curr-V)>= 0) { Min(Sum, V, curr-V); min = Sum[curr-V]+1; } else { min = Sum[curr]; } if(Sum[curr]>min) { Sum[curr]=min; cout<<"Value of Sum["<<curr<<"] is"<<min<<"\n"; } } } }
int answer = 0;
ReplyDeletefor(int i = 0; i < sizeof(denom); i++)
{
int tempAnswer += amount % denom[i];
amount -= tempAnswer * denom[i];
answer += tempAnswer;
}
cout << answer;
sort then use greedy algorithm
ReplyDeleteCode fails with:
ReplyDeletedenom = { 4, 7, 11};
amount = 48;
Answer is 3+2+2=7
Code will print: 12
in your example minimum required is 5 (11+11+11+11+4) coins. But your code prints 12 coins.?
ReplyDeleteActually the correct answer is 5
ReplyDelete11 + 11 + 11 + 11 + 4
Solve with dynamic programming. I have used an arbitrary limit of 500 and allocated unneccesary space. Optimize it.
static uint MinCount(uint number)
{
int a = 4;
int b = 7;
int c = 11;
if (number > 500)
return 0xffffffff;
uint[] array = new uint[501];
for (int i = 1; i <= number; i++)
{
if (i == a || i == b || i == c)
{
array[i] = 1;
continue;
}
uint min = 0xffffffff;
if (i - a > 0)
{
if (min > array[i - a])
min = array[i-a];
}
if (i - b > 0)
{
if (min > array[i - b])
min = array[i - b];
}
if (i - c > 0)
{
if (min > array[i - c])
min = array[i - c];
}
if (min != 0xffffffff)
min++;
array[i] = min;
}
return array[number];
}
The denom input is not specified.The code may not work for all inputs also. However in this case if the denom = {11,7,4} then it will be optimal solution.
ReplyDelete4*11 + 1*4 = 5 coins
The algo is not complete. If u see, the 1st value in denom always makes for more number of coins, then the second(zero or more)... Wat happens in case of amount = 40 ?
I think ans will be 10*4 which is not optimal.
Optimal(maybe) = 3*7 + 1*11 + 2*4 = 6 coins.
Dynamic programming is req
sorting the denom array before the finding the no of coins
ReplyDeleteprivate void find() {
int modValue = 0;
int divValue = 0;
int noOfCoins = 0;
sortTheDenomArray();
for (int i = 0; i < denomination.length; i++) {
if (amount >= denomination[i]) {
divValue = amount / denomination[i];
modValue = amount % denomination[i];
amount = modValue;
noOfCoins = noOfCoins + divValue;
System.out.println(divValue + " " + denomination[i]);
}
}
if (amount != 0) {
System.out.println("We dont have enough denominations");
}else{
System.out.println("No of min coins:" + noOfCoins);
}
}
// MINIMUM NO OF COINS
ReplyDeleteint denom[] = {1,5,10,50,100,500,1000};
int length = sizeof(denom)/sizeof(int);
int noofcoins = 0;
int Amount = 999;
for(int i = length -1 ; i >= 0 ; i--){
noofcoins = noofcoins + Amount / denom[i];
Amount = Amount % denom[i];
}
cout << "no of coins :" << noofcoins << endl;
The above algorithm is incorrect.. Lets take an example as amount to be 34 and denomination as just [10,8]
ReplyDeleteAccording to above algorithm it will give value as 10+10+10 and then it will say We dont have enough denominations. Where as ideally it should be 10+8+8+8.
@Above:
ReplyDeleteI totally agree with your approach. Just one suggestion:
sortTheDenomArray() method should sort the array in descending order.
Hope this helps....
ReplyDeletepublic int getDenominations(int amt,int[] denomArray)
{
int c =0;
int s = 0;
Arrays.sort(denomArray);
boolean f = false;
int m = 0;
int r =0;
int pc = 0;
for(int i=denomArray.length-1;i>=0;i--)
{
r = amt - s;
if(amt%denomArray[i]==0)
{
if(pc==0 || pc>amt/denomArray[i])
pc = amt/denomArray[i];
System.out.println("pc_-> "+pc);
f=true;
// continue;
}
if(denomArray[i]<=r)
{
m = r/denomArray[i];
c=c+m;
s = s + m*denomArray[i];
System.out.println("sum -> "+s +"Count -> "+c);
if(s==amt)
{
f=true;
break;
}
}
}
if(f==true)
{
if(pc!=0 && pc<c)
return pc;
else
return c;
}
else
return 0;
//return c;
}
the above method returns 0, if we don't have enough denominations....
None of these are the solutions. Its a recursive algorithm. The problem with any of the algo's that "Take as many of the biggest denomination" is that they can break the mathematics when using strange denomenations.
ReplyDeleteex:
denom = {5,10,13,20}
amount = 35;
Most of the above mentioned algo's would try
35 - 20x1= 15
15 - 13x1 = 2;
BROKEN!!!
Here's my solution
int Algo2(int * denom, int n1, int amount)
{
if(amount == 0 )
{
return 0;
}
int min = -1;
for(int i=0; i< n1; i++)
{
if(amount < denom[i])
continue;
int numCoin = Algo2(denom,n1,amount - denom[i]) +1 ;
if(numCoin == 0)
continue;
if(numCoin < min || min == -1)
{
min = numCoin;
}
}
return min;
}
The above algorithm is not an efficient and smart algorithm. For example if the amount is 120 and the denominations is {2,4,6}. It will a lot of time to compute the minimum denominations.
Deleteint denominations(int *deno, int n1, int amount){
Deleteint min=-1;
int numofcoins;
for(int i=n1;i>=0;i--){
if(amount<deno[i])
continue;
numofcoins = amount/deno[i];
amount -= numofcoins*deno[i];
if(amount==0)
return numofcoins;
else{
while(amount !=0 && numofcoins !=0){
int temp = denominations(deno,n1-1,amount);
if(temp == -1){
amount += deno[i];
numofcoins--;
}else{
numofcoins += temp;
return numofcoins;
}
}
}
}
return min;
}
Dim a(8), amount, answer, tempanswer, inti
ReplyDeletea(0) = 1
a(1) = 2
a(2) = 5
a(3) = 10
a(4) = 20
a(5) = 50
a(6) = 100
a(7) = 500
a(8) = 1000
answer = 0
amount = Sheets("Sheet1").Cells(1, 1)
For inti = UBound(a) To 0 Step -1
tempanswer = Fix(amount / a(inti))
answer = answer + tempanswer
amount = amount - tempanswer * a(inti)
Next
MsgBox answer
See the simple solution:
ReplyDeletepublic class MaxDenomination
{
private static int coins = 0;
private static int getMinimunCoins(int[] denom, int amount, int startDenom)
{
int localCoins = 0;
while( amount - localCoins * denom[startDenom] >= denom[startDenom])
{
coins++;
localCoins++;
}
if(amount - localCoins* denom[startDenom] > 0 )
{
getMinimunCoins(denom, amount - localCoins* denom[startDenom], ++startDenom);
}
return coins;
}
public static void main(String[] args)
{
int denom [] = {5,2,1};
System.out.println(MaxDenomination.getMinimunCoins(denom, 48, 0));
}
}
This is wrong. try for inputs {10,9,1} and find minimum coins for 153. The algorithm returns 18 coins however 153 can be obtained using only 17 coins (9*17=153)
DeleteJohn, please explain your algorithm.
ReplyDeleteThanks in advance!!
this solution is correct but only works when the denom is in sorted order else it wont.
ReplyDeletevoid Min(int Sum[], int V, int curr);
ReplyDeleteint main()
{
int V[10];
int n, Sum[20];
int S=0;
cout<<"Enter the number of coins\n";
cin>>n;
for(int i=0; i>V[i];
cout<<"\n";
}
cout<<"Enter the Sum\n";
cin>>S;
for(int k=0;k<20;k++)
{
Sum[k]=10000;
}
Sum[0]=0;
for(int i = 0; i=0)
{ if(curr==0)
{
Sum[curr]=0;
}
else
{
if((curr-V)>= 0)
{
Min(Sum, V, curr-V);
min = Sum[curr-V]+1;
}
else
{
min = Sum[curr];
}
if(Sum[curr]>min)
{
Sum[curr]=min;
cout<<"Value of Sum["<<curr<<"] is"<<min<<"\n";
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
ReplyDelete{
int denoms[] = {5, 4, 3 };
int distributions[] = {0, 0, 0, 0, 0, 0, 0};
num_of_denominations = sizeof(denoms)/sizeof(int);
int amount;
std::cout<<"Enter the amount :";
std::cin>>amount;
if( find_denominations(amount, denoms, distributions, 0) )
{
std::cout<<"Denominations: \n";
for( int i= 0; i "<<distributions[i]<<std::endl;
}
else
{
std::cout<<"Cannot form this amount..."<<std::endl;
}
getch();
return 0;
}
///---------- Sani-------------