A tiny chip holds the number x and can do only one thing: multiply two values it has already
computed (possibly the same value twice) and keep the product. Every value it holds is a power of
x, so the chip really just adds exponents: starting from the exponent list [1], each
multiplication appends a + b where a and b are exponents already in the list.
Return the fewest multiplications needed until the exponent n is in the list, i.e. until the chip
holds x ** n. For n = 1 no multiplication is needed.
Examples
Input: n = 1
Output: 0
Input: n = 15
Output: 5
Explanation: 1, 2, 4, 5, 10, 15. (Squaring and multiplying by x as in the binary method
needs 6: 1, 2, 3, 6, 7, 14, 15.)
Input: n = 23
Output: 6
Explanation: for example 1, 2, 3, 5, 10, 20, 23.
Constraints
1 <= n <= 300
Goals
- Search for the shortest sequence by trying depth limits 1, 2, 3, ... in turn
- Prune with an upper bound on how far the sequence can still grow