The Change-O-Matic is a deterministic machine with a single goal: to provide change. That is, you throw in a banknote or a coin, and the machine throws out a bunch of smaller coins with the same total value.
More precisely, the Change-O-Matic operates as follows:
The machine contains several large stacks of coins. The values of these coins are given as a int outputValues. For the purpose of this problem we may assume that the
machine contains an infinite number of coins of each of these values. One of the available values is always 1.
The customer may throw in any coin or banknote with value greater than 1. The machine will output a set of at least two coins with the same total value.
If there are multiple ways to satisfy this requirement, the machine prefers the one where the total number of output coins is minimized.
If there are still multiple ways, the machine prefers the one that is lexicographically maximal (see Notes for a precise definition).
You have a single banknote, and its value is given as a long inputValue. You would like to change it into coins of value 1 each.
Return the number of times you have to throw something into the machine.