Fewest Coins Combination
Updated
Problem statement
You are given an array coins of distinct coin values and an integer amount. You may use any number of coins of each value.
Find a way to make exactly amount with the fewest coins, and return it as an array counts of the same length as coins, where counts[i] is how many coins of value coins[i] you use.
If several ways use the fewest coins, return the one that uses the most coins of the largest value. If that still ties, use the most coins of the second-largest value, and so on.
If amount is 0, every count is 0. If amount cannot be made, return an empty array.
Function
fewestCoinsCombination(coins: int[], amount: int) → int[]Examples
Example 1
coins = [1,5,10,15,20]amount = 3return = [3,0,0,0,0]- Only the coin of value 1 is small enough, so the combination is three 1-coins:
[3,0,0,0,0].
Example 2
coins = [1,5,10,15,20]amount = 30return = [0,0,1,0,1]- The fewest coins is 2, and two combinations reach it: 20 + 10 and 15 + 15.
- The tie goes to the one with more coins of the largest value, 20, so the answer uses one 20 and one 10:
[0,0,1,0,1].
Example 3
coins = [10,4]amount = 7return = []- Sums of 4s and 10s are always even, so 7 cannot be made and the answer is an empty array.
Constraints
1 <= coins.length <= 101 <= coins[i] <= 104- All values in
coinsare distinct. 0 <= amount <= 104
More Bloomberg LP Phone Screen questions
- N-ary Index-Path Encoder and DecoderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Trapping Rain WaterPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Word SearchOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Recommend Films from Viewers Who Watched Everything You DidPHONE SCREEN · Seen Nov 2026
- Track New Values in Sorted OrderPHONE SCREEN · Seen Nov 2026
- Design Browser HistoryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Sparse Vector and Matrix OperationsPHONE SCREEN · Seen Oct 2026
- Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Decode StringPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
- Jump GamePaytm · PHONE SCREENPaytm interview questions
- Query Words Within K PositionsPalantir · PHONE SCREENPalantir interview questions
- House RobberVisa · PHONE SCREENVisa interview questions
- Best Improvement Period of at Least K IntervalsAmazon · PHONE SCREEN
- Longest Increasing SubsequenceAngel One · PHONE SCREEN
- Match Shops and BuyersGoogle · PHONE SCREENGoogle interview questions
- Maximum Product of a Contiguous SubarrayLinkedIn · PHONE SCREENLinkedIn interview questions
- Minimum Cost for a Target WeightPace Stock Broking Services · PHONE SCREEN
- Minimum-Cost Color SequenceOpenAI · OA · PHONE SCREENOpenAI interview questions