유사 칸토어 비트열

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

제한사항
1 ≤ n ≤ 20
1 ≤ l, r ≤ 5n
l ≤ r < l + 10,000,000
l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

문제 풀이 과정

문제를 맨 처음 봤을때 구간을 정할수있기 때문에 DP로 풀려고했지만 l의 값이 배열의 크기보다 크기때문에 DP보다는 재귀를 통한 분할 정복 사용하는게 좋아보였다.
내가 구하는 길이는 f(n,k)에서 길이는 f(n,l)-f(n,r-1)이다.
n=1이면 길이는 5 1의 갯수는 4
n=2이면 길이는 25 1의 갯수는 16
n=3이면 길이는 125 1의 갯수는 64
따라서 n=x면 길이는 Math.pow(5,x) 1의 갯수는 Math.pow(4,x)이다.
또한 항상 구간이 5개로 분할되기 때문에 이를 통해 재귀를 실행하면 된다.
이때 중앙구간인 2번구간은 항상 0이기때문에 추가적인 재귀를 실행할 필요가 없다.
코드

class Solution {
    public int solution(int n, long l, long r) {
        
        long answer = sol(n,r)-sol(n,l-1);      
        return (int)answer;
    }
    long sol (int n,long k){
        if(n==1){
            return k<=2?k:k-1;
        }
        long div = (long)Math.pow(5,n-1);
        long muk = (long)Math.pow(4,n-1);
        long loc = k/div;
        
        if(k % div==0) loc-=1;
        
        if(loc<2){
            return  muk*loc + sol(n-1,k-loc*div);
        }else if(loc==2){
            return muk*loc;            
        }else{
            return muk*(loc-1) + sol(n-1,k-loc*div);
        }
        
    }
  
}