FastPrepFewest Bills to Pay Every Amount
Problems/Fewest Bills to Pay Every Amount

Fewest Bills to Pay Every Amount

Jane Street logoJane Street● MediumNEW GRADFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in two Jane Street trading desk operations phone screens, posted in 2022 and 2024. One candidate was asked for the fewest U.S. bills ($1, $2, $5, $10, $20, $50 and $100) that let you pay every whole amount from $1 to $100. The other was asked the same for every amount from $1 to $99, without the bill values in the report.

In the interview it was a mental puzzle with fixed bills. Here your function gets any list of bill values and any n. Requiring a $1 bill, the limits, and the second and third examples are ours. With U.S. bills the answer is 8 for both $100 and $99.

Our version is about 90% the same as the reported question.

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) → int

Examples

Example 1

denominations = [1,2,5,10,20,50,100]n = 100return = 8

Take 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 = 5

Bills 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 = 10

The 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 <= 20
  • 1 <= denominations[i] <= 10^9
  • All values in denominations are different, and one of them is 1.
  • 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

Interview reports that mention this question

  • Jane Street TDO Phone Math Round: 26 Experiences (Part 9 of 10)
  • Jane Street TDOE New Grad Interview Questions: 11 Experiences

Jane Street interview experiences

  • Jane Street TDO UK and Hong Kong: 22 Experiences (Part 10 of 10)
  • Jane Street TDOE US Final Round: 11 Experiences (Part 5 of 10)
  • Jane Street TDOE UK Phone Screen: 15 Experiences (Part 4 of 10)
  • Jane Street TDO Excel and VBA Test: 23 Experiences (Part 8 of 10)
All Jane Street interview questionsSee Jane Street hiring insights
Saved
class Solution {
    public int minBills(int[] denominations, int n) {
      // Write your code here.
    }
}
Checking account…