Top 10 Programming Languages to Learn in 2019

CodeChef's Solutions

# Bytelandian gold coins Problem Solution with Approach – CodeChef

Page Contents

## 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:122 Output:132`

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```