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 spaceseparated 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 = pc\)
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 \(ddelta\) 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:


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


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


We can avoid continuing looking for the solution when denomination is too big
(greater than difference+9
).
Here an example in imperative Rust:


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
nonvalue with the fallback value 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:


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:


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)