0

I've become rusty at the brain teaser questions since I have been using fancy IDEs and C#. I have a solution for this question, but my real question is **How should I deal with the array size?** Assuming I can't use a list. This is written in C#.

The array size could be too small, or just be a waste of memory in its current state. I left out checks for negative coins, etc. so we could just focus on the algorithm. So I want to get rid of this line: `double [] minList = new double[1000];`

Here's the interview question, return the minimum number of coins that sum to a value (-1 if impossible:

```
public static Main(string [] args) {
double[] coins = {0.01, 0.05, 0.10, 0.25};
Console.WriteLine(MinNumberOfCoinsToSum(0.24, coins));
}
public static int MinNumberOfCoinsToSum(double sum, double [] coins)
{
double [] minList = new double[1000];
minList[0] = sum;
for (int i = 1; i < minList.Length; i++)
{
double buffer = minList[i-1];
for (int j = 0; j < coins.Length; j++)
{
if(minList[i-1] - coins[j] >= 0.0)
{
buffer = Math.Min(buffer, minList[i-1] - coins[j]);
}
}
minList[i] = Math.Min(minList[i-1], Math.Round(buffer, 2));
if (minList[i] == 0.0)
{
return i;
}
}
return -1;
}
```

Well Here's an answer taking in what you guys said (though it doesn't return -1 if not found):

```
private static int MinNumberOfCoinsToSumRecursiveDecimalVersion(decimal sum, decimal [] coins)
{
decimal buffer = sum;
for(int i = 0; i < coins.Length; i++)
{
if(sum - coins[i] >= 0)
{
buffer = Math.Min(buffer, sum - coins[i]);
}
}
if (buffer == sum && sum == 0m)
return 0;
if(buffer == sum && sum != 0m)
{
return Int32.MinValue;
}
int result = 1 + MinNumberOfCoinsToSumRecursiveDecimalVersion(Math.Min(buffer, sum), coins);
return result;
}
```

However my real is question is how do I deal with an array size when I do not know the size beforehand. Thanks btw for the decimal note... that would have been embarrassing at an interview.

```
public int MinNumberForCoinSum(int sum, decimal [] coins) {
// I assume there is a custom Util class, but it would be checking null, empty, or any other business requirement
foreach(var verification in VerificationUtil.GetArrayVerifications()) {
verification.Verify(coins);
}
if(sum < 0 ) { Throw new InvalidArgumentException()); }
return MinNumberOfCoinsToSumRecursiveDecimalVersion(sum, coins);
}
```

I don't think that this question requires an array at all- it's just recursive - Chris Shain 2012-04-05 17:52

Also, you will get nowhere with double. Of your denominations, only 0.25 is exactly representable.

`decimal`

is your friend here - David Heffernan 2012-04-05 17:53
This doesn't answer your question, but personally, I wouldn't do it as an array. I'd do it by ordering the list of coins by value, descending, divide the amount by the value of the current coin - Brian Hoover 2012-04-05 17:54

Even better than decimal, use integers.

`int[] coins = {1, 5, 10, 25}`

Chris Farmer 2012-04-05 17:56
I'm curious if they'd throw "fake" coins at you. Having

`coins={1,5,8,10,25}`

would yield incorrect results for `sum=24`

- Austin Salonen 2012-04-05 18:13
Well, if I were in an actually interview I would add another method that had all the verifications of the data i.e. is the array null? Is the array empty? Are some coin values negative (is that okay? - LLL 2012-04-05 18:27

It might also be worth sorting the coin list if the list is large, that way I wouldn't need to run through the entire list everytime - LLL 2012-04-05 18:28

1

The classic solution to deal with unknown array sizes is to use an initial capacity and then start resizing when it gets full. The growth factor is typically 2. This is what most of the growing data structures in the .NET framework do (list, stack, queue etc.)

Thanks, that was the answer I was looking for - LLL 2012-04-05 21:48

0

Forgive if I sound obnoxious: you are way off. The question has nothing to do with resizing arrays. Here is a solution.

```
public static int numberOfCoins(double[] coins, double sum){
int total = 0;
Arrays.sort(coins);
int amount = (int)(sum*100);//convert to int for precision
for(int i=coins.length-1; i>=0 && amount > 0; i--){
int coin = (int)(100*coins[i]);//convert to int for precision
total+=amount/coin;
amount%=coin;
}
if(amount>0)
return -1;
return total;
}//numberOfCoins
```

Test the code with

```
public static void main(String... args){
double[] den = {0.01,.10,.05,.25};
System.out.println(numberOfCoins(den,1.65));
}
```

EDIT TO HANDLE INT CASE:

In that case I recommend overloading the function. by adding below as well

```
public static int numberOfCoins(int[] coins, int sum){
int total = 0;
Arrays.sort(coins);
int amount = sum;
for(int i=coins.length-1; i>=0 && amount > 0; i--){
total+=amount/coins[i];
amount%=coins[i];
}
if(amount>0)
return -1;
return total;
}//numberOfCoins
```

Thanks for the comment. The question was meant to demonstrate a general concept that I forgot. I didn't really care about the interview question. I was re-learning dynamic programming, and this question was just on my mind. I apparently chose a bad question to use as an example - LLL 2012-04-05 21:47

Should it handle cases like: coins = {1, 2, 6, 7}, sum = 12 - fgb 2012-04-06 00:18

@fgb, in that case I recommend overloading the method. See edits in my post - kasavbere 2012-04-06 00:34