ByteLandian challenge from CodeChef

I am trying to go through the problems on CodeChef and came across this problem:


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?

I approached it using the following algorithm:

-
Check if the total amount on gold coin is greater than (Total/2)+(Total/3)+(Total/4), return total amount on gold coin.

-
Otherwise, recursively evaluate the maximum total amounts for (Total/2),(Total/3) and (Total/4) and return the sum total of these maximums.

My attempt:

public class ByteLandGold{

public static void main(String[] args){
        System.out.println("Printing the bytelandian equivalent for:");
        int byteLandCoin = Integer.parseInt(args[0]);
        System.out.println(ByteLandianConversion(byteLandCoin));
}

private static int ByteLandianConversion(int goldCoinAmount){
        int halfValue = (goldCoinAmount/2);
        int thirdValue = (goldCoinAmount/3);
        int fourthValue = (goldCoinAmount/4);

        int totalIntermediate = halfValue + thirdValue + fourthValue;
        if(goldCoinAmount > totalIntermediate)
                return goldCoinAmount;
        else{
                int maxHalfPortion = ByteLandianConversion(halfValue);
                int maxThirdPortion = ByteLandianConversion(thirdValue);
                int maxFourthPortion = ByteLandianConversion(fourthValue);
                return maxHalfPortion+maxThirdPortion+maxFourthPortion;
        }
}
}

One thing that I see in my code is that the recursive steps are calculating the overlapping sub-problems repeatedly. What would be one way to ensure

If you don't want to recompute the overlapping sub-problems, you could use a cache.

Create the cache in your class:

private HashMap resultCache = new HashMap();

Then check it at the top of the function:

if (resultCache.contains(goldCoinAmount)) return resultCache.get(goldCoinAmount);

And before returning a result, cache it:

if(goldCoinAmount > totalIntermediate){
    resultCache.put(goldCoinAmount, goldCoinAmount);
    return goldCoinAmount;
}else{
    int maxHalfPortion = ByteLandianConversion(halfValue);
    int maxThirdPortion = ByteLandianConversion(thirdValue);
    int maxFourthPortion = ByteLandianConversion(fourthValue);

    int result = maxHalfPortion+maxThirdPortion+maxFourthPortion;
    resultCache.put(goldCoinAmount, result);
    return result;
}

Otherwise, your code is really fairly straightforward and thus fairly readable/maintainable. Readability is far more important than raw performance most of the time.

StackExchange Code Review Q#10787, answer score: 6