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

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)
We've worked on this challenge in these gyms: modena 
comments powered by Disqus