K-th Amount a Payout Machine Can Give
Updated
Problem statement
A payout machine has an unlimited supply of coins of each value in coins. Every payout must use coins of one value only. For example, with coins of 4 and 6, the machine can pay 12 as three 4s or as two 6s, but it cannot pay 10, because that needs one 4 and one 6.
So an amount is payable when it is a positive multiple of at least one value in coins. List every different payable amount in increasing order, writing each amount once even if several coin values can pay it. Return the k-th amount in this list, counting from 1.
Function
findKthSmallest(coins: int[], k: int) → longExamples
Example 1
coins = [4,6]k = 5return = 16The payable amounts are 4, 6, 8, 12, 16, 18, 20, ... (multiples of 4 or of 6). The amount 12 can be paid both ways but is listed once. The 5th amount is 16.
Example 2
coins = [7]k = 3return = 21With one coin value, the payable amounts are 7, 14, 21, ..., so the 3rd is 21.
Example 3
coins = [10,3,8]k = 9return = 18The payable amounts in order are 3, 6, 8, 9, 10, 12, 15, 16, 18, ... The 9th is 18.
Constraints
1 <= coins.length <= 121 <= coins[i] <= 40, and all values incoinsare different.1 <= k <= 2 × 10^9
More Rippling Onsite Interview questions
- Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Camel CardsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Limit an Organization Tree's HeightPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Delivery Cost TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Maximum Currency Conversion Along a Simple PathPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Top K Frequent WordsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Future-Effective Employee SalaryONSITE INTERVIEW · Seen Aug 2026
- Filter and Sort Scheduled TasksONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- First Register Overflow TickNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
- XOR ColoringMicrosoft · OAMicrosoft interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Random Pick with Weight Using Recorded DrawsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Insert into a Left-Complete Binary TreeRubrik · ONSITE INTERVIEWRubrik interview questions
- Find the Missing Number from 1 to nHyperVerge · ONSITE INTERVIEW
- Koko Eating BananasTekion · ONSITE INTERVIEWTekion interview questions
- Bayesian Scenario ClassifierAmazon · ONSITE INTERVIEW
- Swap Two Integers Without a Temporary VariableOracle · ONSITE INTERVIEWOracle interview questions
- Add Two Binary StringsPeopleStrong · ONSITE INTERVIEWPeopleStrong interview questions