class Solution {
    public int kthGrammar(int n, int k) {
        int[] arr = new int[n];          //创建数组，记录每行对应数字所在的位置
        int[] zero = {0,1};              //数字0下一行对应的数字
        int[] one = {1,0};               //数字1下一行对应的数字   
        int curr = k-1;                  //记录当前数字的位置，（k-1）表示k索引改为从0开始
        for(int i = n-1;i >=1;--i){      //从第n行遍历到第2行
            if(curr/2 == (curr+1)/2){    //当前位置与同一行下一个位置同时除以2，结果相等
                arr[i] = 0;              //当行数字的位置在第一位:下标[0]
            }else{                       //结果不相等
                arr[i] = 1;              //当行数字的位置在第二位:下标[1]
            }
            curr = curr / 2;             //获取上一行对应的数字
        }
        int num = 0;                     //用于记录每一行对应的数字
        for(int i = 1;i < n;++i){        //遍历每一行
            if(num == 1){                //当前行为数字1
                num = one[arr[i]];       //下一行就取‘10’两个数中对应的一个数
            }else{                       //当前行为数字1
                num = zero[arr[i]];
            }
        }
        return num;                      //最终遍历到第n行后，获取到第k个字符上的数字，返回。
   }
}