Distracted Shopkeeper

See the original problem on HackerRank.

Shopkeepers often round up the change during a purchase so that the change to be given can be a single bill, making it convenient for both the shopkeeper and the customer.

For example, a customer has paid a \(200\) sesterzio bill for a purchase of \(104\) sesterzi. If the customer then gives an additional \(4\) sesterzi, then the cashier will give an exact \(100\) sesterzio bill in change, instead of several bills and coins if the change is \(96\) sesterzi.

They only typically ask for up to \(9\) sesterzi, since any more would be too inconvenient for the customer. Assume that the available bill denominations are: \(20\), \(50\), \(100\), \(200\), \(500\), \(1000\) sesterzi.

The cashier is getting very distracted today because of the decisive football match he often peeks at. You are asked to write a program to help him not make mistakes.

You are given the cost of purchase and the amount the customer has paid, in sesterzi, and you have to return the amount the cashier should ask the customer. If the change can already be represented as a single bill, then return \(0\). If this amount exceeds \(9\) sesterzi, then return \(-1\) instead.

Input Format

The first line of input contains \(t\), the number of purchases. The following lines describe the purchases.

Each purchase is described by a single line containing two space-separated integers, \(c\) and \(p\), denoting the cost of purchase for that customer and the amount the customer has paid, in sesterzi.

Constraints

• \(1 \leq t \leq 50\)
• \(1 \leq c \le p \leq 2000\)

Output Format

For each purchase, print a single line containing a single integer denoting the amount the cashier should ask the customer. If the change can already be represented as a single bill, then print \(0\). If this amount exceeds \(9\), then print \(-1\) instead.

Solutions

First of all, we need to calculate the excess paid:

\(delta = p-c\)

Suppose we have \(p=200\), \(c=104\) then \(delta=96\).

Next, we have to find the first denomination greater than or equal to \(delta\), that is \(100\). Call this \(d\).

Finally, we calculate \(d-delta\) and return \(YES\) if strictly less than to 10 (or less than or equal to 9).

The most interesting part is how we find the first denomination greater than or equal to \(delta\).

Running a loop is very simple and it does solve the problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int howMuchToAsk(int c, int p)
{
    auto delta = p-c;
    for (auto d : denoms)
    {
        auto diff = d - delta;
        if (diff >=0 && diff<10)
        {
            return diff ;
        }
    }
    return -1;
}

At Coding Gym we practice finding patterns and applications of common algorithms. In C++, for example, we can apply find_if:

1
2
3
4
5
6
7
8

int howMuchToAsk(int c, int p)
{
    auto delta = p-c;
    auto it = find_if(begin(denoms), end(denoms), [=](auto d){
       return (d - delta >= 0) && (d - delta < 10);
    });
    return it != end(denoms) ? (*it-delta) : -1;
}

A slightly different way to see the same solution in Python:

1
2
3
4
5
6

denoms = [20, 50, 100, 200, 500, 1000, float('inf')]
for cas in xrange(input()):
    c, p = map(int, raw_input().split())
    d = p - c
    d = min(den - d for den in denoms if den >= d)
    print d if d <= 9 else -1

We can avoid continuing looking for the solution when denomination is too big (greater than difference+9).

Here an example in imperative Rust:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

fn solve(c: i32, p: i32) -> i32 {
    let delta = p - c;

    let mut result = -1;

    for &denom in &[20, 50, 100, 200, 500, 1000] {
        if denom > delta + 9 {
            break;
        }

        if delta <= denom {
            result = denom - delta;
            break;
        }
    }

    result
}

The same concept can be expressed in declarative Rust. Note that take_while stops iterating when the condition is met. skip_while discards all elements that met te condition, but stop checking when the condition is not met . next returns a particolar type: Option<i32>. It express a result that may not exist. The expression inside map is evaluated only if next returns some value. unwrap_or just extracts the value (if there is one) or replace the non-value with the fallback value -1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

fn solve(c: i32, p: i32) -> i32 {
    let delta = p - c;

    [20, 50, 100, 200, 500, 1000]
        .iter()
        .skip_while(|&&denom| denom < delta)
        .take_while(|&&denom| denom <= delta + 9)
        .next()
        .map(|&denom| denom - delta)
        .unwrap_or(-1)
}

While this code may seem inefficient, due to many function calls, actually the compiler optimizes it in unexpected ways. Here an x86_64 assembly generated by Rust compiler:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

solve:
        sub     esi, edi
        mov     eax, 20
        cmp     esi, 20
        jle     .LBB0_7
        mov     eax, 50
        cmp     esi, 51
        jl      .LBB0_7
        mov     eax, 100
        cmp     esi, 101
        jl      .LBB0_7
        mov     eax, 200
        cmp     esi, 201
        jl      .LBB0_7
        mov     eax, 500
        cmp     esi, 501
        jl      .LBB0_7
        mov     eax, 1000
        cmp     esi, 1001
        jl      .LBB0_7
        mov     eax, -1
        ret
.LBB0_7:
        mov     ecx, eax
        sub     ecx, esi
        add     esi, 9
        cmp     esi, eax
        mov     eax, -1
        cmovge  eax, ecx
        ret

Another interesting way consists in using lower bound, that is, basically, a binary search. On a sorted sequence, it does return in \(O(logN)\) the first element greater than or equal to a certain input element. For this small dataset it does not outperform the linear scan (rather, it’s probably worse), but it’s instructive to apply and know. In C++ we can simply write:

1
2
3
4
5
6
7
8
9

vector<int> denoms = {20, 50, 100, 200, 500, 1000, INT_MAX};

int howMuchToAsk(int c, int p)
{
    auto delta = p-c;
    auto lb = lower_bound(begin(denoms), end(denoms), delta);
    delta = *lb-delta;
    return delta < 10 ? delta : -1;
}

Adding INT_MAX to the end is a simple trick to hadle automatically the case when lower_bound would go beyond the last element.

Surprisingly for some people, the computational cost of all the above solutions is constant (not considering the cost of reading the input that is clearly linear), because the array of denominations is fixed.

Important facts of this excercise:

• we can change/add denominations easily by working only on the denominations array (we don’t change the algorithm)
• using a simple loop is fine
• the problem gets more complicated if the cashier may return a combination of denominations (e.g. 1x20 + 2x50)