Programmers_148652.java

package programmers.lv2;

public class Programmers_148652 {
    public static void main(String[] args) {
        Programmers_148652 test = new Programmers_148652();
        int n = 2;
        int l = 4;
        int r = 17;
        int result = test.solution(n, l, r);
        System.out.println("result: " + result);
    }

    public int solution(int n, long l, long r) {
        int answer = (int) recurCount(n, l, r);
        return answer;
    }

    public long recurCount(int n, long l, long r) {
        if (n == 0) {
            return 1;
        }

        long length = (long) Math.pow(5, n);
        long blockLen = length / 5;

        long result = 0;

        for (int i = 0; i < 5; i++) {
            long start = i * blockLen + 1;
            long end = (i + 1) * blockLen;

            if (i == 2)
                continue;
            if (end < l || start > r)
                continue;

            long newL = Math.max(l, start) - start + 1;
            long newR = Math.min(r, end) - start + 1;

            result += recurCount(n - 1, newL, newR);
        }

        return result;
    }
}