# How to divide a number by specific set of numbers so the result is always zero

Hey guys !

I am working on little roulette game where the player places chips and must reach a score with the lowest chips possible. The thing I am trying to accomplish is to make the game finds how many chips player must use to reach that score, for, in the end screen, display how player did and how the game would do it !

My values are 35, 17, 11, 8 and 5 ! I tried to divide my score with my first value, 35, if the score allows it so if its value is greater or equal to 35, then the logical path in my head would be using the remainder, divide by 17, 11, 8, or 5 if possible, but the thing is, sometimes this doesn’t work, like for example if my score is 70, the game will find out that the lowest number of chips to use will be 2 as follow 2 x 35, right ? But it would do the same with 71, with 1 left since it doesn’t fit any other values I set. However i want to reach 0 each time!. The lowest number of chips for 71 would be 1 x 35, 1 x 17, 1 x 11, 1 x 8, 0 x 5, so 4 in total ! I tried mixing % and / but can’t get something working… Here’s something I tried at first

``````int myScore = some_value;
int remainder, chipNb35, chipNb17, chipNb11, chipNb8, chipNb5;

if (myScore >= 35)
{
chipNb35 = myScore / 35;
remainder = myScore % 35;

if (remainder < 35 && remainder >= 17)
{
chipNb17 = remainder / 17;
remainder = remainder % 17;
}
// and so on
}
``````

I don’t know if everything is clear enough to understand… If it is, I would really appreciate having a main guide line for me to investigate and try by myself first before dying from a seizure and ask for serious help !

Thanks in advance This sounds like a classic scenario for a “Change Calculator”. Since your goal is finding the fewest necessary value units to reach your goal, you can use them accordingly.

[Borrowing a reasonably-shortened formatting example], it might look something like this:

``````public struct Chip
{
string name;
int value;

public Chip(string name, int value)
{
this.name = name;
this.value = value;
}
}

// ...

public Chip[] chipTypes = new Chip[]
{
new Chip("chipNb35", 35),
new Chip("chipNb17", 17),
new Chip("chipNb11", 11),
new Chip("chipNb8", 8),
new Chip("chipNb5", 5),
new Chip("chipNb1", 1)
};

// ...

// When using it:
int[] minimumScore = new int[chipTypes.Length];
// Make a copy of the total before messing with it
int processedTotal = totalValue;
for(int i = 0; i < chipTypes.Length; i++)
{
minimumScore _= processedTotal / chipTypes*.value;*_
``````

* // Since we stored the values already, a multiplication and subtraction*
* // should be cheaper to calculate than a division (modulo)*
processedTotal -= minimumScore * chipTypes*.value;*
}

// Simple example of showing the result
Debug.Log(string.Format(“{0} can be broken down to:”, totalValue));
for(int i = 0; i < chipTypes.Length; i++)
{
_ if(minimumScore > 0)
* {
Debug.Log(string.Format(“{0} ({1}): {2} → {3} chips”, chipTypes.name, chipTypes.value, chipTypes.value * minimumScore, minimumScore));
}
}*

The output should look something like:_

102 can be broken down to:
chipNb35 (35): 70 → 2 chips
chipNb17 (17): 17 → 1 chips
chipNb8 (8): 8 → 1 chips
chipNb5 (5): 5 → 1 chips
chipNb1 (1): 2 → 2 chips
_*: c# - How to make change calculator more simple - Stack Overflow

If you get a remainder, you do the checks for if the remainder is greater than any of your chips. If it can’t find any chips smaller than the remainder, it should take 1 off and add that chip’s value to the remainder and do the checks again.

Like with the example that you gave of 71, after finding that none of the chips are greater/equal to 1, it will reduce the number of 35 chips from 2 to 1, and then the remainder will be 36. Then it will check the chips again (but leave 35 out of it of course)

Basically it should keep doing these checks in a while loop (while the remainder is not equal to 0).

I’ve quickly implemented an bottom up solution that should work with any number of coins and should output the optimal solution:

``````public class CoinStack
{
public int coinValue;

public int totalCount;
public CoinStack next = null;
public override string ToString()
{
if (coinValue == 0)
return "No solution";
var sb = new System.Text.StringBuilder();
sb.Append(coinValue);
for (var cur = this.next; cur != null && cur.coinValue > 0; cur = cur.next)
sb.Append(", ").Append(cur.coinValue);
return sb.ToString();
}
public CoinStack[] Tally()
{
Dictionary<int, CoinStack> dict = new Dictionary<int, CoinStack>();

for (var current = this; current != null && current.coinValue > 0; current = current.next)
{
CoinStack c = null;
if (!dict.TryGetValue(current.coinValue, out c))
{
c = new CoinStack { coinValue = current.coinValue, totalCount = 0 };
}
c.totalCount++;
}
var values = dict.Values;
CoinStack[] result = new CoinStack[values.Count];
values.CopyTo(result,0);
return result;
}
}

public class CoinDB
{
private int[] coins;
private List<CoinStack> stack = new List<CoinStack>();
public CoinDB(params int[] aCoins)
{
coins = aCoins;
stack.Add(new CoinStack { coinValue=0, totalCount=0 });
}
public CoinStack GetChange(int aAmount)
{
if (aAmount < 1)
return null;
// requested number not yet in our DB
if (aAmount >= stack.Count)
{
// add missing values up to our current amount
for (int i = stack.Count; i <= aAmount; i++)
{
var newNode = new CoinStack { totalCount = aAmount + 1 };
for (int n = 0; n < coins.Length; n++)
{
int coinValue = coins[n];
int remainder = i - coinValue;
// if the remainder is negative, there's no solution with this coin, so try the next
if (remainder < 0)
continue;
var prev = stack[remainder];
// if the remainder amount does not have a solution, try the next coin
if (prev.totalCount == -1)
continue;
// found solution of length "count"
int count = prev.totalCount + 1;
if (count < newNode.totalCount)
{
// the new solution is better than the old one, so replace it
newNode.coinValue = coinValue;
newNode.next = prev;
newNode.totalCount = count;
}
}
// if after we tried all coins we still have no solution, there is no solution for this value
if (newNode.coinValue == 0)
{
newNode.totalCount = -1;
}
}
}
return stack[aAmount];
}
}
``````

Note the CoinDB class is meant to be created once for a set of coins. It will remember all intermediate values. You can call the “GetChange” method several times and the internal DB will grow if necessary. Yes, finding the optimal solution requires some memory, however it’s not that much after all. The CoinStack instances will form a tree of nodes which when traversed give you the actual solution. I’ve added the “Tally” method to actually count each individual coin and provide a compact solution.

I’ve even tried it with a value around 1 million and it performs well on my pc. (ps: it takes almost 30000 coins with value of 35 to get over a million ^^).

My test code currently looks like this:

``````    var sw = new System.Diagnostics.Stopwatch();
sw.Start();
var coinDB = new CoinDB(35, 17, 11, 8, 5);
var res = coinDB.GetChange(1046873);
sw.Stop();
var getChangeTime = sw.ElapsedMilliseconds;

sw.Start();
Debug.Log("CompleteSolution: " + res);
sw.Stop();
var debugPrintTime1 = sw.ElapsedMilliseconds;

sw.Start();
var coinList = res.Tally();
sw.Stop();
var TallyTime = sw.ElapsedMilliseconds;

sw.Start();
foreach (var c in coinList)
{
Debug.Log(""+c.totalCount + " x " + c.coinValue);
}
sw.Stop();
var debugPrintTime2 = sw.ElapsedMilliseconds;
Debug.Log(
"getChangeTime: " + getChangeTime + "
``````

"+
"debugPrintTime1: " + debugPrintTime1 + "
" +
"TallyTime: " + TallyTime + "
" +
"debugPrintTime2: " + debugPrintTime2 + "
");

ps: the value of “1046873” can be split up into

``````29910 x 35
1 x 8
3 x 5
``````

pps: don’t try too many of those large numbers as the “CompleteSolution” debug log will actually log 29910 times the string "35, " into the editor log. The console window will trucate the message.