Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Shubhaluxumy loves Binary Number

Last Updated on March 25, 2022 by Ria Pathak

Binary Search

Medium

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given two numbers `N`(number of rows) and `I`(index of a row), such that given a `0` in the 1st row and then keep replacing `0` with `01` and 1 with `10` in the consecutive rows. print the Ith index value of the Nth row.

NOTE: Each row index starts from `1`.

#### For Example:

``````Input :  N = 5, I = 13

Output : 0

Explanation :

1st row     0
2nd row     01
3rd row     0110
4th row     01101001
5th row     0110100110010110

Therefore, 0 is the 13th bit in the 5th row``````

See original problem statement here

Can we use `Recursion` here ?

Yes, We see a pattern that is generated over here in each iteration so `Recursion` can used.

### SOLVING APPROACH:

1. The idea is to use `Binary Search`.
2. First, check If the value of `N` and `I` are both equal to `1`, if `Yes` return `0`.
3. Else recursively check the value of `I` in (1 to 2N-1) positions as Nth row contains 2N-1 values. Also maintain a `flag` variable for the current value.
4. Calculate `mid` value of the interval i.e. `mid = (low + high)/2`
5. Check if `low` becomes equal to `high`, return current value i.e. `flag`
6. Else if `I` is greater than `mid`, then `I` can only lie in the right subarray. So we recur for the right half. Also toggle the value of `flag`.
7. Else (`I` is less than `mid`) recur in the left half with the same value of `flag`.
8. `Time Complexity` of this solution will be `logarithmic` as `Binary Search` is used.

### ALGORITHM:

``````if N = 1 and I = 1
print 0
else
print solve(1, 2^(n-1), 0, I)

solve(low, high, flag, I)

mid = (low + high) / 2

if (low = high)
return flag

else if(I < mid)
return solve(low, mid, flag, I)

else
return solve(mid+1, high, flag, I)
``````

### SOLUTIONS:

```#include <stdio.h>

int getKthBit(int l, int r, int curr, int K){
int mid = (l + r) / 2;

if(l == r)
return curr;

if(K <= mid)
return getKthBit(l, mid, curr == 0 ? 0 : 1, K );
else
return getKthBit(mid + 1, r, curr == 0 ? 1 : 0, K);
}

int main()
{

int t;
scanf("%d",&t);
while(t--)
{
int N,I;
scanf("%d %d", &N, &I);
if(N==1 && I==1)
printf("0\n");
else
printf("%d\n", getKthBit(1, 1 << (N - 1), 0, I));
}

return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;

int getKthBit(int l, int r, int curr, int K){
int mid = (l + r) / 2;

if(l == r)
return curr;

if(K <= mid)
return getKthBit(l, mid, curr == 0 ? 0 : 1, K );
else
return getKthBit(mid + 1, r, curr == 0 ? 1 : 0, K);
}

int main()
{

int t;
cin>>t;
while(t--)
{
int N,I;
cin>>N>>I;
if(N==1 && I==1)
cout<<0<<endl;
else
cout<< getKthBit(1, 1 << (N - 1), 0, I)<<endl;
}

return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
static int getKthBit(int l, int r, int curr, int K){
int mid = (l + r) / 2;

if(l == r)
return curr;

if(K <= mid)
return getKthBit(l, mid, curr == 0 ? 0 : 1, K );
else
return getKthBit(mid + 1, r, curr == 0 ? 1 : 0, K);
}
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0)
{
int N = sc.nextInt();
int I = sc.nextInt();
if(N==1 && I==1)
System.out.println("0");
else
System.out.println(getKthBit(1, 1 << (N - 1), 0, I));
t--;
}
}
}
```
```def getKthBit(l, r, curr, K):

mid = (l + r) // 2

if(l == r):
return curr

if(K <= mid):

if curr == 0:
return getKthBit(l, mid, 0, K )

else:
return getKthBit(l, mid, 1, K )

else:

if curr == 0:
return getKthBit(mid + 1, r, 1, K)

else:
return getKthBit(mid + 1, r, 0, K)

for _ in range(int(input())):

n, i = map(int, input().split())

if n == 1 and i == 1:
print(0)

else:
print(getKthBit(1, 1 << (n - 1), 0, i))
```

[forminator_quiz id="1021"]

This article tried to discuss Binary Search. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.