# Bytelandian Gold Coins | CodeChef Solution

Hello coders, today we are going to solve Bytelandian Gold Coins CodeChef Solution whose Problem Code is COINS.

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 Format

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

## Output Format

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

Example

Sample Input

``````12
2``````

Sample Output

``````13
2``````

Explanation

You can change 12 into 6, 4 and 3, and then change these into 6+4+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 out of them. It is better just to change the 2 coin directly into 2.

## Solution – Bytelandian Gold Coins

### C++

```#include<bits/stdc++.h>
#define ll long long
using namespace std;

unordered_map<ll, ll> mp;

ll solve(ll n) {
if(n<2) {
return n;
}

if(mp.count(n)) {
return mp[n];
}

mp[n] = max(n, solve(n/2)+solve(n/3)+solve(n/4));

return mp[n];
}

int main() {
ll n;
while(cin>>n)
cout<<solve(n)<<'\n';
}```

### Python

```# cook your dish her
dp={0:0,1:1,2:2,3:3,4:4}

while(True):
try:
n=int(input())
def solve(n,dp):
if(n in dp):
return dp[n]
else:
out=max(n,solve(n//2,dp)+solve(n//3,dp)+solve(n//4,dp))
dp[n]=out
return out

(solve(n,dp))
print(dp[n])
except:
break
```

### Java

```/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main(String[] args) {
final HashMap<Long,Long> map = new HashMap();
Scanner sc = new Scanner(System.in);

while (sc.hasNextLong()) {
long N = sc.nextLong();
long max = find_max(N, map);
System.out.println(max);
}
}

static long find_max (long n, Map<Long,Long> map)
{
if(n ==0|| n==1) return n;
if(map.containsKey(n)) return map.get(n);
long max = Math.max(n, find_max(n/2,map) + find_max(n/3,map) + find_max(n/4,map));
if(n<10000) map.put(n,max);
return max;
}

}
```

Disclaimer: The above Problem (Bytelandian Gold Coins) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.