Bytelandian gold coins Problem Solution with Approach – CodeChef

Problem Statement

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?

---

Input

The input will contain several test cases (not more than 10). Each test case is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your coin.

---

Output

For each test case output a single line, containing the maximum amount of American dollars you can make.

---

Example

Input:
12
2 
Output:
13
2

You can change 12 into 6, 4 and 3, and then change these into 6+6+4+3=3=13. If you try changing the coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later you can get no more than 1 coin so it is better to exchange 2 coins for 2 dollars.

---

Approach to Solution

This problem is a classic example of Recursive Programming. Here the main idea is to get the maximum sum of coins. For cases where N > number of coins in (N/2+N/3+N/3) we will simply get the change for the exact coin N.

# Dictionary to store the number of coins to their corresponding keys 
array = {0:0,1:1}

def solve(n):
    if n in array:
        return array[n] #retruns the value of the key if found in array
    else:
        array[n] = max(n,solve(n//2)+solve(n//3)+solve(n//4))
        return array[n] 

if __name__ == '__main__':
    # taking the input 
    i = 10
    while(i > 0):
        n = int(input())
        print(solve(n))
        i -= 1

---

Problem link – link