231013 유사 칸토어 비트열

public int solution(int n, long l, long r) {
	return countOnesInRange(n, l, r, 1);
}

public int countOnesInRange(int n, long start, long end, long index) {
	if (n == 0) {
		return 1;
	}

	int numOnes = 0;
	long subIntervalSize = (long) Math.pow(5, (double) n - 1);

	for (int i = 0; i < 5; i++) {
		long subStart = index + subIntervalSize * i;
		long subEnd = index + subIntervalSize * (i + 1) - 1;

		if (i == 2 || end < subStart || start > subEnd) {
			continue;
		}

		numOnes += countOnesInRange(n - 1, start, end, subStart);
	}

	return numOnes;
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/148652