DSA Tracker

Visualize

K-th Symbol in Grammar

Divide and conquer: which half, then flip or copy

time O(n)space O(n) call stack

Building row n by string replacement costs O(2^n) time and space, since each row doubles in length. But the first half of row n is always an exact copy of row n - 1, and the second half is its exact bitwise complement, because that is literally how the replacement rule expands each symbol. So instead of building anything, just ask which half index k falls into: left half, recurse into row n - 1 at the same index; right half, shift the index back by the halfway point and recurse, then flip whatever bit comes back. That is one recursive call per level, so O(n) time and O(n) stack depth.

Details

Animated on: n = 4, k = 5. Row 4 is built by replacing every 0 with 01 and every 1 with 10 in row 3, starting from row 1 = "0". Answer: 1.

Problem:K-th Symbol in GrammarMedium

Divide and conquer: which half, then flip or copy

step 1 / 10

5
[0]

kthSymbol(4, 5): row 4 is row 3 followed by its bitwise complement, split exactly at mid=2^(4-2)=4. k=5 decides which half we're in.

  • n4=0· arr[0] = 5
Pseudocode
1FUNCTION kthSymbol(n, k)
2  IF n = 1
3    RETURN 0
4  mid <- 2^(n - 2)
5  IF k <= mid
6    RETURN kthSymbol(n - 1, k)
7  ELSE
8    RETURN 1 - kthSymbol(n - 1, k - mid)

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. kthSymbol(4, 5): row 4 is row 3 followed by its bitwise complement, split exactly at mid=2^(4-2)=4. k=5 decides which half we're in.
  2. k=5 > mid=4, so index 5 sits in the RIGHT half, which is the bitwise COMPLEMENT of row 3. Shift back into that row's own indexing with k - mid = 1, then invert whatever comes back.
  3. kthSymbol(3, 1): row 3 is row 2 followed by its bitwise complement, split exactly at mid=2^(3-2)=2. k=1 decides which half we're in.
  4. k=1 <= mid=2, so index 1 sits in the LEFT half, which is an exact copy of row 2. No flip needed: recurse straight into kthSymbol(2, 1).
  5. kthSymbol(2, 1): row 2 is row 1 followed by its bitwise complement, split exactly at mid=2^(2-2)=1. k=1 decides which half we're in.
  6. k=1 <= mid=1, so index 1 sits in the LEFT half, which is an exact copy of row 1. No flip needed: recurse straight into kthSymbol(1, 1).
  7. n=1 is the base row, which is always just "0" — kthSymbol(1, 1) returns 0 with no further recursion.
  8. Left half needs no invert, so kthSymbol(2, 1) just copies the answer from kthSymbol(1, 1) = 0.
  9. Left half needs no invert, so kthSymbol(3, 1) just copies the answer from kthSymbol(2, 1) = 0.
  10. Right half inverts: kthSymbol(4, 5) = 1 - kthSymbol(3, 1) = 1 - 0 = 1.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve K-th Symbol in Grammar in the editorAll Recursion problemsBack to roadmap