class Solution {
//Row  Value   numberOfElementsInRow
//1    // 0                    1
//2    // 01                   2
//3    // 0110                 4
//4    // 01101001             8
    
//f(x,k) = f(x - 1, k/2) == 1 ? '10' : '01' = val;
//f(x,k) = k%2 != 0 ? val[0] : val[1];
    
    
    int[] possibility1;
    int[] possibility2;
        
    Solution() {
         possibility1 = new int[2];
        Arrays.setAll(possibility1, p -> p == 0 ? 1 : 0);
         possibility2 = new int[2];
        Arrays.setAll(possibility2, p -> p == 0 ? 0 : 1);
    }
    
    public int kthGrammar(int n, int k) {
        if(n == 1 || k == 1) {
            return 0;
        }
        int val = kthGrammar(n - 1, (k+1)/2);
       
       
        int[] possibility;
        if(val == 1) {
            possibility = possibility1;
        } else {
            possibility = possibility2;
        }
        return (k + 1) % 2 == 0 ? possibility[0] : possibility[1];
    }
}