Maximum Value from Recursive Coin Exchange
Updated
Problem statement
Starting with one nonnegative integer value n, choose independently for each value x either to keep x unchanged, or to exchange it into three values floor(x/2), floor(x/3) and floor(x/4). You may repeat exchanges on any generated value.
Return the largest possible sum of the values eventually kept. Keeping the original n is allowed. For this exercise, value 0 contributes 0 and need not be exchanged further; all operations use integer division.
Function
maxExchangeValue(n: int) → intExamples
Example 1
n = 12return = 13Exchange 12 into 6,4,3. Their optimal kept total is 13, greater than keeping 12. Further exchanges cannot improve these values, so the maximum is 13.
Example 2
n = 11return = 11Exchanging 11 gives 5+3+2=10, and these smaller values gain nothing from further exchange. Keeping the original 11 is better, so return 11.
Constraints
- For this exercise, assume 0 <= n <= 1000000.
More Morgan Stanley Online Assessment questions
- Three-Resource 0/1 KnapsackOA · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Maximum Total of Nonadjacent RatingsOA · Seen Jul 2026
- Count Shipment SchedulesOA · Seen Apr 2026
- Delete and EarnOA · Seen Apr 2026
- Interleave Array HalvesOA · Seen Apr 2026
- Get Patch SequenceOA · Seen Feb 2025
- String Subsequences 🐳OA · Seen Mar 2024
- Binary Tree Level OrderOA · Seen Feb 2024
- Merge IntervalsOA · Seen Feb 2024
Similar questions at other companies
- 0/1 KnapsackConfluent · OAConfluent interview questions
- Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
- Minimum Cost to Tile a Strip with Widths 1, 2, and 3Infosys · OAInfosys interview questions
- Frog Paths Without Long RunsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Cities on Shortest Delivery RoutesMathWorks · OAMathWorks interview questions
- Count Lucky TicketsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions
- Longest Subsequence That Is a SubstringBooking.com · OA
- Count Routes Through Four Shop TypesOpenAI · OAOpenAI interview questions
- Maximum Subarray SumStraive · OA
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)