โ† Adobe questions

Coin Exchange and Replacement DP

Filed under Adobe

Free read 2 of 3

f(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

  1. f(n) = max(n, f(n/2) + f(n/3) + f(n/4)).

Solution

O(N) time, O(N) space

Python
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.