Rounding amount with available set of denominations

Question

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;
}

Answer 1

I am assuming that you are looking for a performant solution with a relatively small amount of denominations b (e.g. less than 100 denominations). While the amount a and the denominations d[i] can be quite large (e.g. less than 10^6).

1. Sort d ascending and remove duplicates. When rounding down only keep the values smaller or equal than a and when rounding up keep only the smallest value greater or equal than a and discard the greater ones.

2. (Optional) remove all numbers which are a multiple of some other number O(b^2).

3. Calculate the greatest common divisor gcd of the denominations. You can use the Euclidean algorithm starting with the first two numbers then calculate the greatest common divisor of the result and the third number and so on. Of course you can stop as soon as you reach one.

4. Divide a by gcd, round like you want to round the result (using integer division, rounding down: a /= gcd, rounding up: a = (a + gcd - 1) / gcd).

5. Divide all denominations by gcd (d[i] /= gcd). Now the greatest common divisor of all denominations is one and therefore it is guaranteed that a Frobenius number exists (all amounts greater than that number can be built and require no rounding). While doing so you can also check if the new value leads to a % d[i] == 0 and immediately return a * gcd if so.

6. Create a hash set for the values which can be built. It is better than an array because the array is potentially wasting a lot of space (remember the Frobenius number). Add zero to the set.

7. Create a variable n for the current number, initialize with smallest denomination: n = d[0].

8. If n can be built with any of the available denominations, in other words the set contains any of n - d[i] then proceed with the next step. Otherwise increase n by one and repeat this step unless n == a and you are rounding down, then you can return the last number that could be built multiplied by gcd immediately. You could also remove n - d[b - 1] from the set each time because this value will not be requested any more.

9. If n >= a return n * gcd (can only be true when rounding up, rounding down would have returned the result in step 8. already). Else if (a - n) % d[0] == 0 return a * gcd. This check is even better than looking for the Frobenius number (the number after which d[0] - 1 consecutive values can be built), it is more or less the equivalent (d[0] - 1 consecutive values means the difference between one of them and a modulo d[0] has to be zero) but could return much faster. Else increase n by one and continue with step 8.

An example with d = {4, 6} and a = 9999 (or any other big odd number) shows the advantages of this algorithm. It is easy to see that odd numbers can never be built and we would fill up the whole set with all even numbers except 2. But if we divide by gcd we get d = {2, 3} and aUp = 5000 and aDown = 4999. The Frobenius number for {2, 3} is 1 (the only number which cannot be built), so after at most 3 (first number where all modulos are covered) steps (instead of 10000) the modulo would be zero and we would return a * gcd which gives 9998 or 10000 depending on rounding direction, which is the correct result.

---

Here is the code with test included. I did six runs on my crappy notebook and it took 90, 92, 108, 94, 96 and 101 seconds (edit: early loop escape if current denomination greater than current number && n - d[i] >= 0 halves the times and gives an average of about 45s) for 7200 random roundings (3600 in each direction) with combinations of different amounts of denominations (range 2 to 100), dMax (range 100 to 10^6) and aMax (range 10^4 to 10^6), (see the code at the bottom for the exact values). I think the time for the random number generation and output can be neglected, so with this input and the given ranges the algorithm rounds about 160 numbers per second on average (edit: see thirty times faster version below).

public static final int round(int a, int[] d, boolean up) {
    d = d.clone(); // otherwise input gets changed
    Arrays.sort(d);
    if (a < d[0])
        return up ? d[0] : 0;
    int count = 0;
    for (int i = 0; i < d.length; i++) {
        if (d[i] == 0)
            continue;
        for (int 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];
    int gcd = euclid(d[1], d[0]);
    for (int i = 2; i < count && gcd > 1; i++)
        gcd = euclid(d[i], gcd);
    if (up)
        a = (a + gcd - 1) / gcd;
    else
        a /= gcd;
    for (int i = 0; i < count; i++) {
        d[i] /= gcd;
        if (a % d[i] == 0)
            return a * gcd;
    }
    Set<Integer> set = new HashSet<>();
    set.add(0);
    int last = 0;
    for (int n = d[0];; n++) {
        if (!up && n > a)
            return last * gcd;
        for (int 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;
            }
        }
    }
}

public static final int euclid(int a, int b) {
    while (b != 0) {
        int h = a % b;
        a = b;
        b = h;
    }
    return a;
}

public static final int REPEAT = 100;
public static final int[] D_COUNT = {2, 5, 10, 20, 50, 100};
public static final int[] D_MAX = {100, 10000, 1000000};
public static final int[] A_MAX = {10000, 1000000};

public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Random r = new Random();
    for (int i = 0; i < REPEAT; i++) {
        for (int j = 0; j < D_COUNT.length; j++) {
            for (int k = 0; k < D_MAX.length; k++) {
                for (int l = 0; l < A_MAX.length; l++) {
                    int[] d = new int[D_COUNT[j]];
                    for (int m = 0; m < d.length; m++)
                        d[m] = r.nextInt(D_MAX[k]);
                    int a = r.nextInt(A_MAX[l]);
                    System.out.println(round(a, d, false));
                    System.out.println(round(a, d, true));
                }
            }
        }
    }
    System.out.println((System.currentTimeMillis() - start) / 1000 + " seconds");
}

---

As it turns out @Koray's edit 7 is about three times faster for the given input (only for very large gcds my algorithm above is faster). So to get the ultimate algorithm I replaced the dynamic programming part of my algorithm by that of @Koray (with some improvements). It worked, it is roughly ten times faster than edit 7 and thirty times faster than the algorithm above. Which would give about 5000 roundings per second (very rough estimation) on average.

private static int round(int a, int[] d, boolean up) {
    d = d.clone();
    Arrays.sort(d);
    if (a < d[0])
        return up ? d[0] : 0;
    int count = 0;
    for (int i = 0; i < d.length; i++) {
        if (d[i] == 0)
            continue;
        if (a % d[i] == 0)
            return a;
        for (int j = i + 1; j < d.length; j++)
            if (d[j] > 0 && 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];
    int gcd = euclid(d[1], d[0]);
    for (int i = 2; i < count && gcd > 1; i++)
        gcd = euclid(d[i], gcd);
    if (gcd > 1) {
        if (up)
            a = (a + gcd - 1) / gcd;
        else
            a /= gcd;
        for (int i = 0; i < count; i++) {
            d[i] /= gcd;
            if (a % d[i] == 0)
                return a * gcd;
        }
    }
    int best = !up ? d[count - 1] : ((a + d[0] - 1) / d[0] * d[0]);
    if (d[count - 1] > a) {
        if (d[count - 1] < best)
            best = d[count - 1];
        count--;
    }
    Stack<Integer> st = new Stack<Integer>();
    BitSet ba = new BitSet(a + 1);
    for (int i = 0; i < count; i++) {
        ba.set(d[i]);
        st.push(d[i]);
    }
    while (st.size() > 0) {
        int v1 = st.pop();
        for (int i = 0; i < count; i++) {
            int val = v1 + d[i];
            if (val <= a && !ba.get(val)) {
                if ((a - val) % d[0] == 0)
                    return a * gcd;
                ba.set(val, true);
                st.push(val);
                if (!up && val > best)
                    best = val;
            } else if (val > a) {
                if (up && val < best)
                    best = val;
                break;
            }
        }
    }
    return best * gcd;
}