leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

kth_symbol_grammar.c (868B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 779. K-th Symbol in Grammar
#include <stdio.h>
#include <stdlib.h>

/*
 * we build a table of 'n' rows (1-indexed) we start by writing 0 in the first
 * row. now in every subsequent row, we look at the previous row and replace
 * each occurence of zero with '01', and each occurence of 1 with '10'. for
 * example for 'n = 3', the first row is the 0, the second row is the 01, and
 * the third row is 0110. given two integer 'n' and 'k', return the k'th
 * (1-indexed) symbol in the n'th row of a table of 'n' rows.
 */

int kthGrammar(int n, int k) {
  if (n == 1)
    return 0;
  if (k % 2 == 1)
    return kthGrammar(n - 1, (k + 1) / 2);
  else
    return (kthGrammar(n - 1, k / 2) == 0) ? 1 : 0;
}

int main() {
  printf("%d\n", kthGrammar(1, 1)); // expect: 0
  printf("%d\n", kthGrammar(2, 1)); // expect: 0
  printf("%d\n", kthGrammar(2, 2)); // expect: 1
}