K-th Symbol in Grammar

medium math recursion bit-manipulation

Problem

Row 1 is '0'. Each subsequent row replaces 0 -> 01 and 1 -> 10. Return the K-th symbol (1-indexed) in row N.

InputN=4, K=5

Output1

Row 4 starts 0110100110010110; position 5 is 1.

input

def kthGrammar(N, K):
    return bin(K-1).count('1') & 1

function kthGrammar(N, K) {
  let n = K - 1, c = 0;
  while (n) { c += n & 1; n >>>= 1; }
  return c & 1;
}

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

int kthGrammar(int N, int K) {
    return __builtin_popcount(K-1) & 1;
}

Explanation

You could build the entire row by repeatedly applying the rules, but that grows exponentially. Instead there is a beautiful one-line answer: the K-th symbol equals the parity (odd/even count) of the set bits in K - 1.

Here is the intuition. Each new row doubles the previous one: the left half is a copy, and the right half is the copy with every bit flipped. So whether a symbol ends up flipped depends on how many times its position fell into a "right half" as the rows were built.

Writing the position K - 1 (0-indexed) in binary, each 1 bit means "this position was in the flipped right half at that level". Since the original symbol is 0, an even number of flips leaves it 0 and an odd number makes it 1. That is exactly popcount(K-1) & 1.

Example: N = 4, K = 5. Then K - 1 = 4, which is 100 in binary — one set bit. The parity is 1, so the answer is 1, matching the actual row 4.

Counting bits in a number takes about O(log K) time, and notice N is not even needed for the formula.

Time: O(log K) Space: O(1)