# K-th Symbol in Grammar

Moderate
0/80
Average time to solve is 20m
Contributed by

## Problem statement

You are given two integers, ‘N’ and ‘K’. Your task is to return the ‘K-th’ bit in row ‘N’ of the given sequence.

Sequence: The first row contains a single bit ‘1’. In each subsequent row, we look at the previous row and replace each ‘1’ with ‘10’ and each ‘0’ with ‘01’.

Example:
``````N = 4, K = 5

Given sequence:
The previous row’s ‘1’ becomes ‘10’, and ‘0’ becomes ‘01’ for each subsequent row. The contents of each row are:
Row 1: 1
As, ‘1’ => ‘10’, So ‘1’ (row 1) => ‘10’ (row 2)

Row 2: 10
As ‘1’ => ‘10’& ‘0’ => ‘01’,So ‘10’ (row 2) => ‘1001’ (row 3)

Row 3: 1001
As ‘10’ => ‘1001’ & ‘01’ => ‘0110’, So ‘1001’ (row 3) => ‘10010110’ (row 4)

Row 4: 10010110
The ‘5-th’ bit in row ‘4’ is ‘0’. Return ‘0’ as the answer.
``````
Note:
``````Both ‘K’ and ‘N’ have 1-based indexing.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 10 ^ 4
1 <= N <= 30
1 <= K <= 2 ^ (N - 1)

Where ‘T’ is the number of test cases, ‘N’ is the row number, and ‘K’ is the bit index.

Time limit: 1 second.
``````

#### Sample input 1:

``````2
3 4
5 8
``````

#### Sample output 1:

``````1
0
``````

#### Explanation of sample input 1:

``````Test Case 1:
N = 3, K = 4

Given sequence:
Row 1: 1
Row 2: 10
Row 3: 1001
The ‘4-th’ bit in row ‘3’ is 1. Return ‘1’ as the answer.

Test Case 2:
N = 5, K = 8

Given sequence:
Row 1: 1
Row 2: 10
Row 3: 1001
Row 4: 10010110
Row 5: 1001011001101001
The ‘8-th’ bit in row ‘5’ is ‘0’. Return ‘0’ as the answer.
``````

#### Sample input 2:

``````2
3 2
2 1
``````

#### Sample output 2:

``````0
1
``````
Console