[프로그래머스] 유사 칸토어 비트열 (JAVA)

문제설명

남아는 n 번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해졌습니다.
n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return 하도록 solution 함수를 완성해주세요.

solution.java

class Solution {
    public int solution(int n, long l, long r) {
        return countOne(n, l, r, 1);
    }

    public int countOne(int n, long s, long e, long idx) {
        if(n==0) {
            return 1;
        }
        int num = 0;
        long part = (long)Math.pow(5, n-1);
        for(int i=0 ; i<5 ; i++) {
            if(i==2 || e<(idx+part*i) || (idx+part*(i+1)-1)<s) continue;            
            num += countOne(n-1, s, e, idx+part*i);
        }
        return num;
    }
}

해설

5^0 : 1
5^1 : 11011
5^2 : 11011 11011 00000 11011 11011
n이 커져도 규칙이 생긴다.
1 = 0
5 = 12+1 ~ 13
25 = 52+1 ~ 53
125 = 252+1 ~ 253
위와 같이 가운데 범위에는 무조건 0이 되기 때문에 1만 range 안에 있는 값 중 가운데 값을 제외하고 1만 찾는다.