FastPrepReturn a Minimum-Coin Change Breakdown
Problems/Return a Minimum-Coin Change Breakdown

Return a Minimum-Coin Change Breakdown

Datadog logoDatadog● MediumFULLTIMEPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: Reports ask for minimum change, sometimes returning the count for each denomination, and follow up with arbitrary denominations where greedy can fail. This exercise combines those requirements; input ordering, deterministic ties, zero and impossible cases, and bounds are specified for practice. The core task matches the reports at about 90%.

Make amount using the fewest coins from the denominations in coins. Every denomination is available in unlimited quantity. Return an integer array with one count per denomination, in the same order as coins.

If several combinations use the minimum number of coins, prefer the one using more coins of the largest denomination; if still tied, compare counts at the next smaller denomination, and continue downwards. Return an empty array if making the amount is impossible. For amount zero, return one zero for each denomination.

The input may use arbitrary positive denominations. Choosing the largest coin first is sufficient for some systems, including [1,5,10,25], but is not a general solution.

Function

minimumCoinBreakdown(coins: int[], amount: int) → int[]

Examples

Example 1

coins = [1,5,10,25]amount = 33return = [3,1,0,1]

Use one 25, one 5, and three 1 coins. Their value is 25 + 5 + 3 = 33 and their count is 5, which is minimum. Counts follow the input denomination order.

Example 2

coins = [1,3,4]amount = 6return = [0,2,0]

Two 3 coins make 6. Taking a 4 first would require two 1 coins and use three coins. Return the two-coin solution.

Example 3

coins = [2,4]amount = 3return = []

Every available coin has even value, so no combination can total the odd amount 3. Return an empty array.

Constraints

  • 1 <= coins.length <= 20
  • 1 <= coins[i] <= 1000
  • The denominations are strictly increasing.
  • 0 <= amount <= 10000

More Datadog problems

  • Query Log MatchPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Delete a Filesystem TreePHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
  • Grouped-Query Attention Forward PassPHONE SCREEN · Seen Jun 2026
All Datadog interview questionsSee Datadog hiring insights
Saved
public int[] minimumCoinBreakdown(int[] coins, int amount) {
    // Write your code here.
}
Checking account…