K-th Symbol in Grammar

MediumMathmath

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Build a table of rows of bits. Row 1 is 0. Each following row is produced from the previous one by replacing every 0 with 01 and every 1 with 10. So row 2 is 01, row 3 is 0110, row 4 is 01101001, and row n has 2^(n-1) symbols. Given n and k, return the k-th symbol (1-indexed) of row n as the integer 0 or 1. Row 30 has over 500 million symbols, so do not build the rows; aim for O(n) or O(log k) time.

Examples

Input: n = 1, k = 1
Output: 0
Row 1 is 0.
Input: n = 3, k = 3
Output: 1
Row 3 is 0110 and its third symbol is 1.
Input: n = 4, k = 5
Output: 1
Row 4 is 01101001 and its fifth symbol is 1.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More math problems