Rounding amount with available set of denominations

Viewed 743

This isn't regular rounding thing which rounds up or down based of a single value. I would want to have a function where I pass the amount as integer and denominations as array of integer. What that function should return to me is a nearest possible integer value achievable with passed array of denominations. Whether to round up or down will again be sent as a parameter.

Code:

var amount = 61; // for. e.g.
int[] denoms = [20, 50]; // for. e.g.
bool roundUp = true;
amount = RoundAmount(amount, denoms, roundUp);

Expected result :

RoundAmount function should return me the nearest possible amount achievable with denoms that I have passed.

  1. If roundUp = true, The return value should be 70, because 70 = 20+50 and amount 70 can be achieved by one note of 20s and one note of 50s.
  2. If roundUp = false, It should have returned 60, because 60 = 20+20+20 and amount 60 can be achieved by 3 notes of 20s

What I got so far :

I was only reached to the point where I can manage to round the amount up or down based on a single integer (and not the array of integers)

public int RoundAmount(int amount, int value, bool roundUp)
{
   if (roundUp)
      amount = amount - (amount % value) + value;
   else
      amount = amount - (amount % value)

   return amount;
}

Edit:

I have another recursive function which checks if amount is achievable or not, Only if amount isn't achievable, RoundAmount function is called.

So in my example, amount = 70 will never be the input because 70 is achievable with available denoms and I won't call the RoundAmount in that case.

Solution: (Thanks to maraca and Koray)

I'm glad its working with long numbers though it wasn't original requirement.

private static long RoundAmount_maraca(long a, long[] d, bool up)
{
    d = d.ToArray();
    Array.Sort(d);

    if (a < d[0])
        return up ? d[0] : 0;
    long count = 0;
    for (long i = 0; i < d.Length; i++)
    {
        if (d[i] == 0)
            continue;
        for (long j = i + 1; j < d.Length; j++)
            if (d[j] % d[i] == 0)
                d[j] = 0;
        if (d[i] > a && !up)
            break;
        d[count++] = d[i];
        if (d[i] > a)
            break;
    }
    if (count == 1)
        return (!up ? a : (a + d[0] - 1)) / d[0] * d[0];
    long gcd = euclid(d[1], d[0]);
    for (long i = 2; i < count && gcd > 1; i++)
        gcd = euclid(d[i], gcd);
    if (up)
        a = (a + gcd - 1) / gcd;
    else
        a /= gcd;
    for (long i = 0; i < count; i++)
    {
        d[i] /= gcd;
        if (a % d[i] == 0)
            return a * gcd;
    }
    var set = new HashSet<long>();
    set.Add(0);
    long last = 0;
    for (long n = d[0]; ; n++)
    {
        if (!up && n > a)
            return last * gcd;
        for (long i = 0; i < count && n - d[i] >= 0; i++)
        {
            if (set.Contains(n - d[i]))
            {
                if (n >= a)
                    return n * gcd;
                if ((a - n) % d[0] == 0)
                    return a * gcd;
                set.Add(n);
                last = n;
                break;
            }
        }
    }
}
private static long euclid(long a, long b)
{
    while (b != 0)
    {
        long h = a % b;
        a = b;
        b = h;
    }
    return a;
}
5 Answers
Related