Yahoo Interview Question
Software Engineer / DevelopersCountry: United States
is the csTable the number of solutions or the number of coins?
if it is the number of solutions, then returning csTable[sum][m], in the end is wrong.
if it is the number of minimal coins then, this is wrong:
for (int j = 0; j <= m; j++) {
csTable[0][j] = 1;
}
and should be =0
classical coin sum problem. DP solution. O(n).
public static int coinSum(final int[] coins, final int sum) {
final int m = coins.length;
final int[][] csTable = new int[sum + 1][m + 1];
// base cases: if m == 0 then no solution for any sum
for (int i = 0; i <= sum; i++) {
csTable[i][0] = 0;
}
// base case: if sum = 0 then there is only one solution for any input set: just take none of each of the items.
for (int j = 0; j <= m; j++) {
csTable[0][j] = 1;
}
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= m; j++) {
// solutions excluding coins[j]
final int s1 = csTable[i][j - 1];
// solutions including coins[i]
final int s2 = (i - coins[j - 1]) >= 0 ? csTable[i - coins[j - 1]][j] : 0;
csTable[i][j] = s1 + s2;
}
}
return csTable[sum][m];
}
Famous min coin denomination problem. can be found on net.
private static void minCoinChange(int[] denom, int n) {
int[] s = new int[n+1];
int[] c = new int[n+1];
int size = denom.length;
s[0]=0;
c[0]=0;
int coin=1;
for(int p=1;p<=n;p++)
{
int min=Integer.MAX_VALUE;
for(int d=0;d<size;d++)
{
if(p>=denom[d])
{
if((1+c[p-denom[d]]) < min)
{
min = 1+c[p-denom[d]];
coin=denom[d];
}
}
}
s[p]=coin;
c[p]=min;
}
System.out.println("min coins: " + c[n]);
printMinCoinChange(c,s,n);
}
This is a dynamic programming problem.
Code:
#include <stdio.h>
void calc_min( int arr[], int len, int sum ){
int i=0;
int j=0;
int mat[len][sum+1];
for( i=0; i<len; i++){
for( j=0; j<=sum; j++){
mat[i][j] = 99;
}
}
for( j=0; j<=sum; j++ ){
if( j==arr[0] )
mat[0][j] = 1;
else
mat[0][j] = 99;
}
for( i=0; i<len; i++)
mat[i][0] = 0;
for( i=1; i<len; i++ ){
for( j=1; j<=sum; j++ ){
int x = 99;
int y = 99;
if(j-arr[i]>=0){
x = 1 + mat[i-1][j-arr[i]];
}
y = mat[i-1][j];
mat[i][j] = (x<y?x:y);
printf("%d\t", mat[i][j]);
}
}
printf("%d\n", mat[3][12]);
}
int main(void) {
int arr[] = { 2,3,5,7 };
int len = sizeof(arr) / sizeof(int);
int sum = 12;
calc_min( arr, len, sum );
return 0;
}
Time complexity = O(sum*num_coins)
Space complexity = O(sum*num_coins)
Dynamic Programming problem:
Code:
#include <stdio.h>
void calc_min( int arr[], int len, int sum ){
int i=0;
int j=0;
int mat[len][sum+1];
for( i=0; i<len; i++){
for( j=0; j<=sum; j++){
mat[i][j] = 99;
}
}
for( j=0; j<=sum; j++ ){
if( j==arr[0] )
mat[0][j] = 1;
else
mat[0][j] = 99;
}
for( i=0; i<len; i++)
mat[i][0] = 0;
for( i=1; i<len; i++ ){
for( j=1; j<=sum; j++ ){
int x = 99;
int y = 99;
if(j-arr[i]>=0){
x = 1 + mat[i-1][j-arr[i]];
}
y = mat[i-1][j];
mat[i][j] = (x<y?x:y);
printf("%d\t", mat[i][j]);
}
}
printf("%d\n", mat[3][12]);
}
int main(void) {
int arr[] = { 2,3,5,7 };
int len = sizeof(arr) / sizeof(int);
int sum = 12;
calc_min( arr, len, sum );
return 0;
}
Complexity = O(no_of_coins*sum)
If I understand the problem correctly - this is a variant of the Knapsack01 problem where the goal is to find the maximum value with the minimum number of items. In other words, out of all possible combinations which result in the maximum value (in our case the maximum value is the sum), we want to find the one with the minimum number of items.
In the original Knapsack01 problem we define an array dp[number_of_coins+1][sum+1] and each array element dp[i][j] represents the maximum sum which can be achieved using the first i coins (without repetitions):
dp[i][j] = (j>=coin_value[i-1]) ? Max(dp[i-1][j-coin_value[i-1]+coin_value[i-1],dp[i-1][j]) : dp[i][j-1]
In order to calculate the minimum number of coins for the maximum sum, we'll store both the sum and the corresponding number of coins for each dp[i][j].
Now, whenever dp[i-1][j-coin_value[i-1]].sum() + coin_value[i-1] == dp[i-1][j].sum() we'll choose the value for dp[i][j] according to the minimum number of coins:
1. if dp[i-1][j-coin_value[i-1]].coins() + 1 < dp[i-1][j].coins() then
dp[i][j].coins dp[i-1][j-coin_value[i-1]].coins() + 1
2. Otherwise, dp[i][j].coins = dp[i-1][j].coins
3. For both (1) and (2), dp[i][j].sum = dp[i-1][j-coin_value[i-1]].sum() + coin_value[i-1] (it can also be dp[i-1][j] because both values are equal).
Basically, every time we need to decide between two equal maximum sums (one that includes the current coin and that doesn't) we choose the one which can be achieved with less coins according to dp[i][j].coins() value.
Here's an implementation of this idea (admittedly, I haven't tested it thoroughly):
private static class SumCoins {
private int sum;
private int coins;
public SumCoins(int sum, int coins){
this.sum = sum;
this.coins = coins;
}
public int getSum(){return sum;}
public int getCoins(){return coins;}
public void setSum(int sum){this.sum = sum;}
public void setCoins(int coins){this.coins = coins;}
}
public static int findMinimumCoins(int[] coins, int sum){
if ((coins==null) || (sum<=0)){return 0;}
SumCoins[][] dp = new SumCoins[coins.length+1][sum+1];
for (int i=0;i<dp.length;i++){
for (int j=0;j<dp[i].length;j++){
dp[i][j] = new SumCoins(0,0);
}
}
for (int i=1;i<dp.length;i++){
for (int j=1;j<dp[i].length;j++){
if (j>=coins[i-1]){
if ((dp[i-1][j-coins[i-1]].getSum()+coins[i-1] > dp[i-1][j].getSum()) ||
((dp[i-1][j-coins[i-1]].getSum()+coins[i-1] == dp[i-1][j].getSum()) &&
(dp[i-1][j-coins[i-1]].getCoins()+1 < dp[i-1][j].getCoins()))){
dp[i][j].setCoins(dp[i-1][j-coins[i-1]].getCoins()+1);
dp[i][j].setSum(dp[i-1][j-coins[i-1]].getSum()+coins[i-1]);
}
else {
dp[i][j].setCoins(dp[i-1][j].getCoins());
dp[i][j].setSum(dp[i-1][j].getSum());
}
}
else{
dp[i][j].setCoins(dp[i][j-1].getCoins());
dp[i][j].setSum(dp[i][j-1].getSum());
}
}
}
return dp[coins.length][sum].getCoins();
}
Complexity: O(n*s) run-time and space complexity.
Note: If the sum cannot be reached using the given coins then the returned value in the code above would be the minimum number of coins for the closest value to sum which can be achieved using the input coins. Using dp[coins.length][sum].getSum() we can determine that value and decide what to do in this case.
Greedy solution will not work in some cases.
If for e.g. if denominations are 1,2,4,5 and you want to make up 8, the greedy algorithm will return (5,2,1), the solution is (4,4).
We need dynamic programming solution.
N - total sum
d - number of coins
change[N+1] - stores change values of sum 1->N
Coins[d] stores coin values
N[0] = 0 //trivial problem with known solution
for i=1 to N do
change[i] = N+1 // ideally infinity, but N+1 is also not possible so we can use it
for j=d to 0 do
// check if current coin is of lesser or equal value of curret sum
// check if we we include the coin, and a best solution for number of coins lower value coin (sum-current_coin) +1 is lesser that current known value starting from N+1
if(Coins[j]<=i and change[i-coins[j]]+1<change[i]) then
change[i] = change[i-coins[j]]+1
end if
end for
end for
return
//O(N*D)
call the method,
S - Sum,
A[] - Denominations
int mincoins = makeChange(S,A.length-1, A);
int makeChange(int amount, int index, int[] Denominations) {
if ( amount <=0 ){
return 0;
}
if ( amount >= Denominations[index]) {
return change(amount-Denominations[index], index, Denominations);
} else{
return change(amount, --index, Denominations);
}
}
call the method as makeChange.
Input - S - Sum, A.length-1, A[] - Denominations
int mincoins = makeChange(S,A.length-1, A);
int makeChange(int amount, int index, int[] Denominations) {
if ( amount <=0 ){
return 0;
}
if ( amount >= Denominations[index]) {
return makeChange(amount-Denominations[index], index, Denominations);
} else{
return makeChange(amount, --index, Denominations);
}
}
Public int countNoOfCoins(int[] coins, int sum)
{
Arrays.sort(coins);
int count =0;
for(int index=coins.length-1;index>=0;index--)
{
if(sum>= coins[index])
{
sum=sum-a[index];
count++;
}
if(sum ==0)
return count;
}
return -1;
}
classical coin sum problem. DP solution. O(n).
- zahidbuet106 May 26, 2014