785. Kth Symbol in Grammar

In the Kth Symbol in Grammar problem, row 1 starts as "0". Each subsequent row is formed by replacing every '0' with "01" and every '1' with "10". Given two 1-indexed integers n (the row number) and k (the position in that row, 1-indexed), return the k-th symbol in row n (as 0 or 1). Implement recursively.

Input: Two integers n and k separated by a comma (1-indexed).

Output: Return an integer: 0 or 1.

Examples

Input: 1, 1
Output: 0
Explanation: Row 1 is '0'.

Input: 2, 2
Output: 1
Explanation: Row 2 is '01'; position 2 is '1'.

Input: 4, 5
Output: 1
Explanation: Row 4 is '0110100110010110'; position 5 is '1'.

Constraints

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

Asked by