SPOJ: COINS – Bytelandian gold coins

Problem Link


Problem Description

In this problem, We can exchange each coin of value n with three coins of value (n/2),(n/3),(n/4).
So, we need to find maximum value we can obtain from a coin of n value.

Concepts Used

This is a straightforward DP problem.


using namespace std;

// long long int as resultant value can be greater than 10^9.
long long int dp[10000005];

long long int coins(long long int n)
    //Base case
        return 0;

    // can't store value greater than 10^7 in an array so use recursion
        return max(n,coins(n/2)+coins(n/3)+coins(n/4));

    // if dp[n] has already been calculated, then return that value.
        return dp[n];

        // calculate the value

        return dp[n];

long long int n;
int main()
        /*function to assign 0 to every location in dp array equivalent to


        but it always intialise the whole array i.e. whole size of dp.

    // to read untill end of file

return 0;


  1. Input the values of n till end of file.
  2. Call the function coins(n) for each value of n.
  3. An array long long int dp[10000005] is declared and the values set to 0. Here the limit of n is 10^9 but we can store only upto 10^7 in an array so we create a dp of 10^7 and for bigger values, we just apply recursive method.
  4. dp[i] represents the maximum amount we can obtain from coin value i.
  5. So, we memoize the coin values in dp and if(dp[i]!=0) means it has already been evaluated, then return dp[i] else evaluate it by considering it as
dp[i]= max(i,coins(i/2)+coins(i/3)+coins(i/4));

    return 0; // This is base case

This content has been helpful to you?

Thanks for contributing!

Yes No