Coin Exchange and Replacement DP
Filed under Adobe
Free read 2 of 3f(n) = max(n, f(n/2) + f(n/3) + f(n/4)).
The question
Given N coins, you can keep them or exchange them for N/2 + N/3 + N/4 coins. Find the maximum value obtainable.
Constraints
- N can be up to 10^6.
- The exchange process is recursive.
- Base case is when N=0.
Examples
- Input
- 12
- Output
- 13
- Why
- 12 -> 6+4+3=13. 13 is better than 12.
Approach
f(n) = max(n, f(n/2) + f(n/3) + f(n/4)).
Use a dictionary or array to store results of f(n) to avoid recomputing.
If n == 0, return 0.
Solution
O(N) time, O(N) space
memo = {0: 0}
def max_coins(n):
if n in memo: return memo[n]
memo[n] = max(n, max_coins(n//2) + max_coins(n//3) + max_coins(n//4))
return memo[n]
Tips
- What they are testing: Ensure memoization is used to avoid redundant calculations.
- Common mistake: Forgetting to compare the current N with the sum of its parts; sometimes keeping the coins is better.
Related Adobe questions
Collected from public candidate posts and coding forums. Updated Nov 2026.