Bytelandian gold coins (WA)

[tanyushonok]

Hello. I've tested a lot and checked with calculator). It seems right, but I get WA. Please give the cue where I'm wrong. Thanks

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedHashMap;
import java.util.Map;

public class Main {

public static Map<Integer, Integer> hm = new LinkedHashMap<Integer, Integer>();

public static int coinExchange(int number) {
    if (number < 12) return number;
    else {
        int result = hm.get(number);
        if (result == 0) {
            result = number/2 + number/3 + number/4;
            hm.put(number, result);
            return result;
        }
        else
            return result;
    }
}

public static void main(String []args){
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try {
        String str;
        while((str = br.readLine()) != null && str.length() != 0) {
            int number = Integer.parseInt(str);
            Main.hm.put(number, 0);
        }
        for (Integer key : Main.hm.keySet()) {
            System.out.println(coinExchange(key));
        }
    } catch (Exception e){
        return;
    }
}

}

[daft_wullie]

Bytelandian Coins can be changed into 1/2, 1/3, 1/4 repeatedly. I cannot see this aspect in your code...

[tanyushonok]

I've tried this code. It gave me wrogh answer as well(

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedHashMap;
import java.util.Map;

public class Main {

public static Map<Integer, Integer> hm = new LinkedHashMap<Integer, Integer>();

public static int coinExchange(int number) {
    if (number < 12) return number;
    else {
        int result = hm.get(number);
        if (result == 0) {
            result = coinExchange(number/2) + coinExchange(number/3) + coinExchange(number/4);
            hm.put(number, result);
            return result;
        }
        else
            return result;
    }
}

public static void main(String []args){
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try {
        String str;
        while((str = br.readLine()) != null && str.length() != 0) {
            int number = Integer.parseInt(str);
            Main.hm.put(number, 0);
        }
        for (Integer key : Main.hm.keySet()) {
            System.out.println(coinExchange(key));
        }
    } catch (Exception e){
        return;
    }
}

}

[daft_wullie]

Hm. And what is the difference? Do you expect the reader to compare your code versions?
The key observation in the COINS problem is that you can change the change. Lets start with a coin of value 24. You change it into coins with 12, 8, 6 value. Now you can change the coin with 12 value and get 6,4,3 value. That sums up to 27. How do you handle this effect in your code?

[tanyushonok]

Thank you, I finally get the task
But still I have a problem. If I test small numbers, I get results of all of them. When I test big numbers, I get results of only one or two checked numbers. Is it because my map is overflow? What can I do?
Thank you)))

public class Main {

public static Map<Integer, Integer> hm = new LinkedHashMap<Integer, Integer>();

public static int coinExchange(int number) {
    if (number < 12) return number;
    int result;
    if (hm.containsKey(number))
        result = hm.get(number);
    else
        result = 0;
    if (result == 0) {
        int exchange = coinExchange(number/2) + coinExchange(number/3) + coinExchange(number/4);
        if (number > exchange)
            result = number;
        else
            result = exchange;

        hm.put(number, result);
    }
    return result;
}

public static void main(String []args){
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try {
        String str;
        while((str = br.readLine()) != null && str.length() != 0) {
            int number = Integer.parseInt(str);
            Main.hm.put(number, 0);
        }
        for (Integer key : Main.hm.keySet()) {
            System.out.println(coinExchange(key));
        }
    } catch (Exception e){
        return;
    }
}

}

[tanyushonok]

P.s. I've changed the type of map: Map hm

[tanyushonok]

from Integer, Integer for Integer, BigInteger

[daft_wullie]

I guess it could be an issue with the stack due to the amount of recursive function calls. I remember struggling with this for my python solution, too. You can try to avoid going too deep in recursion.

[tanyushonok]

I will try. Thank you)))))