How should I practice K-th Symbol in Grammar?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Bloomberg LP onsite interview problems in FastPrep.

Is K-th Symbol in Grammar associated with Bloomberg LP?

FastPrep tags this as a Bloomberg LP onsite interview coding practice problem when the problem catalog has that company and stage context.

K-th Symbol in Grammar

Bloomberg LP● MediumNEW GRADONSITE INTERVIEW

Learn

Problem statement

Row 1 of a binary grammar is 0. Each later row replaces every 0 with 01 and every 1 with 10.

Given n and one-indexed k, return the k-th symbol in row n.

Function

kthGrammar(n: int, k: int) → int

Examples

Example 1

n = 1k = 1return = 0

The first row is 0.

Example 2

n = 4k = 5return = 1

Row 4 is 01101001 and its fifth symbol is 1.

Constraints

1 <= n <= 30.
1 <= k <= 2^(n-1).