https://school.programmers.co.kr/learn/courses/30/lessons/148652
public class Solution {
public static long solution(int n, long l, long r) {
long length = (long) Math.pow(5, n);
return countOnes(n, l - 1, r - 1, length);
}
public static long countOnes(int n, long start, long end, long len) {
if (start >= len || end < 0) {
return 0;
}
if (n == 0) {
return (start < 1 && end >= 0) ? 1 : 0;
}
long subLen = len / 5;
long sum = 0;
// 첫 번째 구간 1(0~subLen-1)
sum += countOnes(n - 1, start, end, subLen);
// 두 번째 구간 1(subLen~2*subLen-1)
sum += countOnes(n - 1, start - subLen, end - subLen, subLen);
// 세 번째 구간 0(2*subLen~3*subLen-1), count = 0
// 네 번째 구간 1(3*subLen~4*subLen-1)
sum += countOnes(n - 1, start - 3 * subLen, end - 3 * subLen, subLen);
// 다섯 번째 구간 1(4*subLen~5*subLen-1)
sum += countOnes(n - 1, start - 4 * subLen, end - 4 * subLen, subLen);
return sum;
}
}