Ctrl K

Largest Unpayable Amount

Medium
An old arcade machine only accepts coins of two denominations, coin_a and coin_b; both are distinct prime numbers. It never gives change, so you can only pay an amount that is made up exactly of such coins. You have an unlimited supply of each. Some small amounts cannot be formed this way, but past a certain point every amount can. Return the largest positive integer amount that cannot be paid.
Example 1
coin_a=3, coin_b=5 → 7

The amounts 1, 2, 4 and 7 cannot be paid. Every amount from 8 up can: 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5, and from there you just keep adding 3s.

Example 2
coin_a=2, coin_b=7 → 5

2s cover every even amount, and odd amounts become payable starting at 7, so only 1, 3 and 5 are out of reach.

Example 3
coin_a=11, coin_b=13 → 119
Constraints
  • 1 < coin_a, coin_b < 10⁴
  • coin_a and coin_b are distinct primes
  • coin_a · coin_b < 10⁵
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsChunks With a Common Divisor MediumSplit by Shared Ends MediumDivisor Chains HardPaths With Exactly One Prime HardLargest Palindrome That Is a Multiple Hard
loading Python…
Input
coin_a=3, coin_b=5
Expected
7

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.