K-th Symbol in Grammar Medium 0 attempts
LeetCode ↗

K-th Symbol in Grammar

Medium BacktrackingRecursion LeetCode

Picture a sequence of rows, numbered starting at 1, where row 1 is just the single digit 0. Each later row is generated from the one before it by scanning left to right and expanding every 0 into 01 and every 1 into 10. Given n and k, work out what digit sits at position k (also 1-indexed) within row n.

Input Format
Implement kthGrammar(n, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
n = 2
k = 1
Output
0

Example 2

Input
n = 4
k = 8
Output
1
Constraints
  • 1 <= n <= 30
  • 1 <= k <= 2^(n-1)
Test Cases (2)
Case 1
Args: [2,1] Expected: 0
Case 2
Args: [4,8] Expected: 1
Topics
BacktrackingRecursion

The first half of row n mirrors row n-1, and the second half is its complement. If k is in the first half, recurse with the same k. If k is in the second half, recurse with k minus the half-size and flip the result.

javascript
function kthGrammar(n, k) {
  if (n === 1) return 0;
  const half = Math.pow(2, n - 2);
  if (k <= half) {
    return kthGrammar(n - 1, k);
  } else {
    return kthGrammar(n - 1, k - half) ^ 1;
  }
}

Time: O(n) Space: O(n) for recursion stack

Saved in this browser only. Private to you.

JavaScript