Description
In grammar row 1 is 0. Each row replaces 0 with 01 and 1 with 10. Given n and k, return the kth (1-indexed) symbol in row n.
Examples
Input:
n = 2, k = 1Output:
0Explanation:
Row 1: 0, Row 2: 01.
Input:
n = 1, k = 1Output:
0Explanation:
Row 1 contains only '0'. The 1st (and only) symbol is 0.
Input:
n = 4, k = 6Output:
1Explanation:
Row 1: 0, Row 2: 01, Row 3: 0110, Row 4: 01101001. The 6th symbol in row 4 is 1.
Constraints
- •
1 ≤ n ≤ 30 - •
1 ≤ k ≤ 2^(n-1)