Find One Symbol in a Repeated Binary Expansion
Company: Deshaw
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Row 1 is "0". To form each next row, replace every 0 with 01 and every 1 with 10. Return the one-indexed kth symbol of row n without building the full row.
```cpp
class Solution {
public:
int kthGrammar(int n, int k);
};
```
### Examples
**Example 1:**
```text
n = 3, k = 4
Output: 0
Explanation: Row3 is 0110.
```
**Example 2:**
```text
n = 4, k = 6
Output: 0
Explanation: Row4 is 01101001, whose sixth symbol is0.
```
### Constraints
- Row number n lies in [1,30].
- Position k satisfies 1 <= k <= 2^(n-1).
### Contract considerations
Preserve row and position indexing.
```hint Read the boundary condition
Which child of a symbol flips its value?
```
### Boundary reminders
Preserve row and position indexing.
Overview: Find One Symbol in a Repeated Binary Expansion. Row 1 is "0". To form each next row, replace every 0 with 01 and every 1 with 10.