Ctrl K

K-th Postage With One Stamp Type

Hard
A post office sells stamps in several denominations, given as stamps; all denominations are different. There is an unlimited supply of each, but an envelope may only carry stamps of a single denomination: three 4-stamps make 12, while a 4 and a 6 together are not allowed. List every amount that can be paid this way, without repeats, in increasing order. Return the k-th amount (counting from 1).
Example 1
stamps=[4, 6], k=5 → 16

Stamps of 4 cover 4, 8, 12, 16, …; stamps of 6 cover 6, 12, 18, … Together that is 4, 6, 8, 12, 16, 18, …, and the fifth amount is 16.

Example 2
stamps=[7, 3, 5], k=6 → 10

The amounts available are 3, 5, 6, 7, 9, 10, …, so the sixth is 10.

Example 3
stamps=[2], k=1000000000 → 2000000000
Constraints
  • 1 ≤ len(stamps) ≤ 15
  • 1 ≤ stamps[i] ≤ 25
  • all values in stamps are distinct
  • 1 ≤ k ≤ 2 · 10⁹
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsPair GCDs by Sorted Position HardGCD Times Sum HardBump Numbers to Fit the Divisors HardThe Lost Ticket EasyN-th Number Divisible by One of Three Medium
loading Python…
Input
stamps=[4, 6], k=5
Expected
16

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