Minimum Winning Rounds with Limited All-In Bets
Updated
Problem statement
John begins with one chip and wins every round. In a round, he may bet one chip, increasing his total by one, or bet all his chips, doubling his total.
He finishes with exactly N chips and uses at most K all-in bets. A bet of one chip is always a regular bet, even when it is his entire balance.
Return the minimum possible number of rounds. Starting with the target balance requires zero rounds.
Function
solution(N: int, K: int) → intExamples
Example 1
N = 8K = 0return = 7The totals are 1,2,3,4,5,6,7,8. All seven rounds are one-chip bets.
Example 2
N = 18K = 2return = 6A shortest sequence is 1,2,3,4,8,9,18. Only 4 to 8 and 9 to 18 are all-in rounds.
Example 3
N = 10K = 10return = 4The totals 1,2,4,5,10 use four rounds and two all-in bets. The initial 1 to 2 bet is regular.
Constraints
1 <= N <= 2147483647.0 <= K <= 100.
More Marshall Wace Online Assessment questions
- Count Letters with Ordered Lowercase and Uppercase OccurrencesOA · Seen Oct 2025
- Maximum Trailing Zeros on a Path with at Most One TurnOA · Seen Oct 2025
- Shortest Subarray Covering an Integer RangeOA · Seen Oct 2025
- Maximum Events in a 60-Second WindowOA · Seen Aug 2025
- Successful Logins from Multiple CountriesOA · Seen Aug 2025
- Maximize Remaining Item Types After Clearing Consecutive ShelvesOA · Seen Nov 2024
- Shortest String After Erasing Equal PairsOA · Seen Nov 2024
- Count Distinct Tags in a Fixed-Radius Circle (Practice Reconstruction)OA · Seen Apr 2024
- Generate Unique Company Email AddressesOA · Seen Apr 2024
- Reconstruct a Two-Row Binary MatrixOA · Seen Apr 2024
Similar questions at other companies
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Server Upgrade PlanningWells Fargo · OAWells Fargo interview questions
- Task Scheduler with CooldownGoDaddy · OA
- Minimize Adjacent Squared-Difference Cost with One InsertionMcKinsey & Company · OAMcKinsey & Company interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimum Values with Even Powers of TwoVisa · OAVisa interview questions
- Minimize Adjacent Squared-Difference Cost with One InsertionMicrosoft · OAMicrosoft interview questions
- Minimum Halvings for Alternating ParityIBM · OAIBM interview questions
- Resource AllocationMaven Securities · OAMaven Securities interview questions
- Return Exact Cash Register ChangeBank of America · OA