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.
Definition
- Class:
- DecimalCoins
- Method:
- pay
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int pay(int[] coins)
- (be sure your method is public)
Constraints
- coins will contain exactly 7 elements.
- Each element of coins will be between 0 and 1000, inclusive.
Examples
{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
{997, 0, 0, 1, 0, 0, 0}
Returns: 998
{997, 0, 1, 1, 0, 0, 0}
Returns: 2098
{999, 0, 0, 1, 0, 0, 0}
Returns: 2000
{0, 0, 0, 0, 0, 0, 0}
Returns: 1
{1000, 1000, 1000, 1000, 1000, 1000, 1000}
Returns: 1111111001
{9, 9, 0, 0, 0, 0, 0}
Returns: 100
{1, 7, 9, 0, 7, 5, 0}
Returns: 2
{808, 1, 0, 0, 0, 3, 0}
Returns: 819
{6, 0, 9, 0, 9, 0, 0}
Returns: 7
{9, 389, 0, 0, 9, 77, 0}
Returns: 3900
{9, 0, 0, 9, 0, 0, 355}
Returns: 10
{9, 3, 748, 0, 0, 9, 0}
Returns: 40
{425, 9, 9, 757, 0, 9, 0}
Returns: 1658416
{180, 9, 388, 310, 9, 1, 0}
Returns: 539071
{9, 6, 0, 0, 0, 925, 0}
Returns: 70
{9, 9, 9, 0, 5, 9, 7}
Returns: 1000
{9, 0, 0, 0, 0, 8, 0}
Returns: 10
{9, 0, 525, 0, 0, 0, 0}
Returns: 10
{876, 0, 0, 9, 9, 0, 0}
Returns: 877
{4, 0, 0, 0, 0, 0, 0}
Returns: 5
{8, 0, 0, 0, 9, 5, 0}
Returns: 9
{9, 9, 0, 9, 0, 9, 639}
Returns: 100
{7, 2, 0, 574, 0, 9, 0}
Returns: 8
{9, 0, 9, 6, 7, 0, 9}
Returns: 10
{9, 0, 9, 0, 5, 9, 0}
Returns: 10
{1, 0, 520, 0, 0, 2, 0}
Returns: 2
{8, 9, 9, 9, 245, 528, 95}
Returns: 9
{6, 9, 0, 9, 9, 831, 9}
Returns: 7
{7, 0, 0, 0, 0, 0, 0}
Returns: 8
{992, 0, 9, 9, 6, 9, 9}
Returns: 70893
{9, 0, 643, 9, 0, 1, 9}
Returns: 10
{263, 0, 5, 0, 0, 0, 0}
Returns: 764
{7, 0, 0, 0, 9, 9, 0}
Returns: 8
{403, 9, 0, 9, 0, 0, 4}
Returns: 494
{210, 9, 0, 9, 258, 9, 0}
Returns: 301
{7, 9, 0, 0, 319, 36, 9}
Returns: 8
{9, 6, 0, 4, 9, 0, 0}
Returns: 70
{9, 9, 0, 0, 9, 0, 9}
Returns: 100
{589, 89, 9, 0, 0, 0, 8}
Returns: 2380
{9, 0, 605, 930, 531, 9, 0}
Returns: 10
{9, 953, 918, 0, 0, 0, 0}
Returns: 101340
{9, 0, 0, 7, 0, 0, 0}
Returns: 10
{9, 0, 0, 0, 0, 9, 9}
Returns: 10
{9, 377, 0, 5, 7, 0, 9}
Returns: 8780
{9, 0, 0, 637, 9, 9, 0}
Returns: 10
{2, 553, 0, 375, 0, 9, 0}
Returns: 3
{9, 0, 9, 281, 0, 9, 0}
Returns: 10
{6, 9, 0, 0, 7, 0, 904}
Returns: 7
{9, 0, 0, 9, 3, 9, 0}
Returns: 10
{1, 4, 9, 658, 4, 0, 0}
Returns: 2
{709, 0, 0, 549, 0, 0, 4}
Returns: 710
{9, 0, 7, 9, 0, 0, 0}
Returns: 10
{4, 772, 4, 9, 0, 9, 0}
Returns: 5
{677, 0, 7, 0, 0, 9, 0}
Returns: 1378
{9, 0, 9, 9, 0, 0, 0}
Returns: 10
{9, 372, 9, 0, 0, 9, 0}
Returns: 4630
{9, 9, 0, 752, 0, 0, 412}
Returns: 100
{9, 8, 0, 283, 0, 9, 0}
Returns: 90
{9, 0, 0, 3, 706, 0, 9}
Returns: 10
{2, 0, 9, 0, 893, 619, 9}
Returns: 3
{3, 9, 0, 9, 9, 729, 9}
Returns: 4
{9, 0, 9, 2, 0, 0, 9}
Returns: 10
{4, 0, 618, 6, 0, 0, 9}
Returns: 5
{575, 0, 0, 9, 0, 7, 0}
Returns: 576
{9, 9, 8, 0, 9, 0, 9}
Returns: 900
{9, 9, 0, 0, 0, 9, 0}
Returns: 100
{753, 0, 264, 9, 0, 0, 9}
Returns: 36154
{249, 9, 0, 9, 0, 0, 0}
Returns: 340
{845, 0, 0, 2, 0, 0, 9}
Returns: 846
{328, 9, 0, 9, 0, 9, 89}
Returns: 419
{9, 9, 0, 213, 6, 0, 0}
Returns: 100
{6, 0, 4, 690, 0, 25, 0}
Returns: 7
{4, 9, 0, 9, 9, 7, 9}
Returns: 5
{2, 0, 9, 505, 9, 0, 0}
Returns: 3
{9, 0, 224, 0, 0, 0, 0}
Returns: 10
{9, 9, 0, 9, 9, 0, 0}
Returns: 100
{221, 9, 0, 9, 0, 109, 9}
Returns: 312
{751, 9, 0, 1000, 0, 0, 0}
Returns: 842
{5, 9, 0, 0, 0, 9, 101}
Returns: 6
{8, 0, 7, 0, 9, 9, 9}
Returns: 9
{9, 900, 9, 2, 0, 0, 0}
Returns: 11910
{9, 6, 621, 3, 340, 0, 0}
Returns: 70
{9, 7, 9, 0, 0, 5, 0}
Returns: 80
{1, 0, 3, 508, 9, 9, 754}
Returns: 2
{9, 9, 0, 9, 0, 6, 0}
Returns: 100
{1, 9, 133, 30, 9, 0, 2}
Returns: 2
{4, 2, 0, 693, 0, 9, 9}
Returns: 5
{9, 0, 4, 0, 0, 9, 0}
Returns: 10
{196, 9, 9, 0, 0, 6, 3}
Returns: 1187
{9, 0, 6, 0, 9, 0, 0}
Returns: 10
{3, 0, 0, 0, 281, 9, 0}
Returns: 4
{718, 9, 0, 9, 0, 0, 0}
Returns: 809
{767, 0, 9, 0, 0, 0, 9}
Returns: 1668
{7, 0, 161, 9, 0, 0, 711}
Returns: 8
{9, 4, 9, 544, 401, 0, 0}
Returns: 50
{999, 0, 0, 999, 0, 0, 0}
Returns: 1000000
{999, 0, 0, 999, 0, 0, 999}
Returns: 1000000000
{99, 0, 99, 0, 99, 0, 0}
Returns: 1000000
{99, 0, 99, 0, 499, 3, 7}
Returns: 12300000
{103, 1, 89, 1, 499, 3, 7}
Returns: 12300014
{103, 1, 89, 0, 499, 3, 7}
Returns: 9014
{1000, 1000, 1000, 1000, 1000, 1000, 1000 }
Returns: 1111111001
{9, 2, 8, 0, 0, 0, 0 }
Returns: 30
{1000, 1000, 1000, 0, 1000, 1000, 1000 }
Returns: 1110111001
{21, 8, 1, 0, 0, 0, 0 }
Returns: 202
{1000, 0, 9, 9, 9, 9, 9 }
Returns: 10000901
{999, 1, 1, 0, 0, 0, 0 }
Returns: 1110
{1000, 7, 9, 9, 9, 9, 9 }
Returns: 10000971
{1000, 7, 9, 9, 0, 0, 0 }
Returns: 10971
{123, 1, 0, 0, 0, 0, 0 }
Returns: 134