779. K-th Symbol in Grammar

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

Note:

1. N will be an integer in the range [1, 30].
2. K will be an integer in the range [1, 2^(N-1)].

一刷
题解：
Observation 2: let f(k) be the value of kth position (0-based), then:
f(2 * k) = 0 {if f(k) = 0} or, 1 {if f(k) = 1} => f(2 * k) = f(k) xor 0
f(2 * k + 1) = 0 {if f(k) = 1} or 1 {if f(k) = 0} => f(2 * k + 1) = f(k) xor 1

class Solution {
    public int kthGrammar(int N, int K) {
        return helper(N-1, K/2, K&1);
    }
    
    private int helper(int row, int K, int isOdd){
        if(row == 1) return 0;
        if(row == 2){
            if(K==1) return 0;
            else return 1;
        }
        if(isOdd==1){
            return helper(row-1, K/2, K&1) ^ 1;
        }else{
            return helper(row-1, K/2, K&1) ^ 0;
        }
    }
}

方法2:
Obervation 3: if binary string of k is used, let k = 1001010, then we have:
f(1001010) = f(100101) ^ 0 = f(10010) ^ 1 ^ 0 = f(1001) ^ 0 ^ 1 ^ 0 = ... = f(0) ^ 1 ^ 0 ^ 0 ^1 ^ 0 ^ 1 ^ 0 = 1 ^ 0 ^ 0 ^1 ^ 0 ^ 1 ^ 0
So, the result is the xor operation on all bits of k. Since 0 does not change xor result, we can ignore all 0s.
f(1001010) = 1 ^ 1 ^ 1 = (1^1) ^ 1 = 0 ^ 1 = 1
f(11110011) = 1 ^ 1^ 1 ^ 1 ^ 1 ^1 = (1 ^ 1) ^ (1 ^ 1) ^ (1 ^1) = 0
Now, it’s easy to tell f(k) = 0 if k has even number of 1s in binary representation, and f(k) = 1 when k has odd number of 1s

public int kthGrammar(int N, int K) {
    return Integer.bitCount(K-1) & 1;
}