Fewest Bills to Pay Every Amount
Updated
Problem statement
You may put any number of bills of each value in denominations into your wallet. You want a wallet from which you can pay every whole amount from 1 to n exactly, by handing over some of its bills, with no change given back.
Return the minimum number of bills such a wallet must hold.
Function
minBills(denominations: int[], n: int) → intExamples
Example 1
denominations = [1,2,5,10,20,50,100]n = 100return = 8Take one $1, two $2, one $5, one $10, two $20 and one $50 bill. The first three pay every amount up to 5, then each new bill extends the range: up to 10, 20, 40, 60 and finally 110, which covers 100. Seven bills are not enough: one bill reaches at most 1, two at most 3, three at most 5, then 10, 20, 40 and 60, so seven bills can never cover every amount up to 100.
Example 2
denominations = [1,3]n = 10return = 5Bills 1, 1, 3, 3, 3 pay every amount up to 2, then 5, 8 and 11. You need two 1 bills, because with only one, amount 2 cannot be paid. Four bills can cover at most 1 + 1 + 3 + 3 = 8, which is less than 10.
Example 3
denominations = [25,10,5,1]n = 99return = 10The order of the denominations does not matter. Four 1 bills pay up to 4. One 5 bill extends that to 9, two 10 bills to 29, and three 25 bills to 104. That is 4 + 1 + 2 + 3 = 10 bills. A 25 bill is only useful once every amount up to 24 can be paid.
Constraints
1 <= denominations.length <= 201 <= denominations[i] <= 10^9- All values in
denominationsare different, and one of them is1. 1 <= n <= 10^9
More Jane Street Phone Screen questions
- Maximum-Scoring Consecutive Tree LevelsPHONE SCREEN · Seen Nov 2026
- Tree Selection and VisibilityPHONE SCREEN · Seen Nov 2026
- Load/Store Arithmetic InterpreterPHONE SCREEN · Seen Oct 2026
- Instrument Stack Language JumpsPHONE SCREEN · Seen Oct 2026
- Run a Stack Language InterpreterPHONE SCREEN · Seen Oct 2026
- Positive-Integer Expression EvaluationPHONE SCREEN · Seen Oct 2026
- Add Two Integers Given as StringsPHONE SCREEN · Seen Sep 2026
- Angle Between Clock HandsPHONE SCREEN · Seen Jul 2026
- Route Length From Two CyclistsPHONE SCREEN · Seen Jul 2026
- Sort TradesPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Integer BreakAmazon · ONSITE INTERVIEW
- Minimum Operations To Reduce To ZeroUber · OAUber interview questions
- Get Minimum OperationsJP Morgan Chase · OAJP Morgan Chase interview questions
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Jump GamePaytm · PHONE SCREENPaytm interview questions
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions
- Minimum Cost for a Target WeightPace Stock Broking Services · PHONE SCREEN
- Minimum Operations to Make Every Array Element OneOtter.ai · PHONE SCREENOtter.ai interview questions
- Jump Game IINavi · PHONE SCREEN
- Best Stock Profit With a Sell FeeKaseya · PHONE SCREEN