313. Symbol in Row K
A tiling machine lays out rows of black (0) and white (1) tiles. Row 1 is the single tile 0. To build the next row, the machine replaces every 0 of the current row by 01 and every 1 by 10, working from left to right. So row 2 is 01, row 3 is 0110 and row 4 is 01101001.
Given the row number n and a position k counted from 1 at the left, return the tile at that position of row n as 0 or 1. Row n has 2^(n-1) tiles, which is far too many to build for large n, so find the answer without constructing the row.
Example 1
- Input:
- n = 5, k = 11
- Output:
- 0
- Explanation:
Row 5 is 0110100110010110 and its 11th tile is 0.
Example 2
- Input:
- n = 6, k = 22
- Output:
- 1
- Explanation:
Tile 22 of row 6 descends from tile 11 of row 5 (a 0) and is the second child of that tile, so it is 1.
Constraints
1 ≤ n ≤ 30
1 ≤ k ≤ 2^(n-1)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)