Shubhaluxumy loves Binary Number

Last Updated on March 25, 2022 by Ria Pathak

CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

Given two numbers N(number of rows) and I(index of a row), such that given a 0 in the 1^st row and then keep replacing 0 with 01 and 1 with 10 in the consecutive rows. print the I^th index value of the N^th 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 2^N-1) positions as N^th row contains 2^N-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))

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.