Doubling Rows of Bits

Medium

Rows of digits are built by a rule. Row 1 is 0. Each next row comes from the previous one by replacing every 0 with 01 and every 1 with 10. For example, row 2 is 01, row 3 is 0110, and row 4 is 01101001. Given a row number row and a position pos (both 1-based), return the digit at position pos of row row. Row 30 has over half a billion digits, so building it outright will not work.

Example 1

row=3, pos=3 → 1

The rows are 0, 01, 0110. The third digit of row 3 is 1.

Example 2

row=4, pos=6 → 0

Row 4 is 01101001, and its sixth digit is 0.

Example 3

row=1, pos=1 → 0

Constraints

1 ≤ row ≤ 30
1 ≤ pos ≤ 2^(row − 1)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Recursion Math

Similar problems

Only Twos Multiplied Easy Only Fours Multiplied Easy A String That Copies Itself Easy A Letter in a Growing Word Hard Adding Digit Lists Medium

Input

row=3, pos=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 53 tests on the server, hidden ones included.