DecimalCoins
SRM 819 · 2021-12-02 · by misof
Problem Statement
In Absurdistan the coin denominations are powers of ten. More precisely, they have coins worth 10^0, 10^1, 10^2, ..., 10^6 dollars. (That is, 1, 10, 100, ..., 1,000,000 dollars.)
Elisha has some coins in her purse: for each i, she has coins[i] coins worth 10^i dollars each.
Calculate and return the smallest amount of dollars Elisha cannot pay exactly using just the coins in her purse.
Constraints
- coins will contain exactly 7 elements.
- Each element of coins will be between 0 and 1000, inclusive.
{7, 3, 1, 0, 0, 0, 0}
Returns: 8
The coins in Elisha's purse are 1, 1, 1, 1, 1, 1, 1, 10, 10, 10, 100. She can pay any amount between 0 and 7, inclusive, but she cannot pay exactly 8, so that is the smallest amount she cannot pay.
{123, 1, 0, 0, 0, 0, 0}
Returns: 134
Elisha's total is 133 dollars, and as most of her money are ones, she can pay each amount between 0 and 133 dollars exactly.
{0, 1, 2, 3, 4, 5, 6}
Returns: 1
Elisha has a lot of money, but with no ones she cannot pay the very simple sum of 1 dollar exactly.
{8, 8, 8, 8, 8, 8, 8}
Returns: 9
{9, 9, 9, 9, 9, 9, 9}
Returns: 10000000
Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DecimalCoins with a public method int pay(vector<int> coins) · 115 test cases · 2 s / 256 MB per case