1726. Base-K Change
A quirky vending machine in a retro arcade only accepts coins whose values are powers of k: 1, k, k^2, k^3 and so on, with an unlimited supply of each. You need to pay exactly amount using as few coins as possible.
Return the minimum number of coins as a long; an amount of 0 needs 0 coins. Always taking the largest coin that still fits is optimal, since k of any smaller coin can be replaced by one bigger coin. The coin count therefore equals the sum of the digits of amount written in base k, which you can compute in O(log amount) time and O(1) space.
Example 1
- Input:
- amount = 10, k = 3
- Output:
- 2
- Explanation:
10 is 101 in base 3, so the best change is one 9-coin and one 1-coin: 2 coins.
Example 2
- Input:
- amount = 0, k = 5
- Output:
- 0
- Explanation:
Nothing to pay needs 0 coins.
Example 3
- Input:
- amount = 255, k = 2
- Output:
- 8
- Explanation:
255 is 11111111 in base 2, so all eight coins 1 to 128 are needed: 8.
Constraints
0 ≤ amount ≤ 1015
2 ≤ k ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(log amount)
- Space
- O(1)