{"id":1006,"date":"2020-06-10T09:46:31","date_gmt":"2020-06-10T09:46:31","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1006"},"modified":"2022-03-25T11:41:20","modified_gmt":"2022-03-25T11:41:20","slug":"shubhaluxumy-loves-binary-number","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/shubhaluxumy-loves-binary-number\/","title":{"rendered":"Shubhaluxumy loves Binary Number"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Binary Search<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given two numbers N<\/code>(number of rows) and I<\/code>(index of a row), such that given a 0<\/code> in the 1st<\/sup> row and then keep replacing 0<\/code> with 01<\/code> and 1 with 10<\/code> in the consecutive rows. print the Ith<\/sup> index value of the Nth<\/sup> row.<\/p>\n

NOTE<\/strong>: Each row index starts from 1<\/code>.<\/p>\n<\/blockquote>\n

For Example:<\/h4>\n
Input :  N = 5, I = 13\n\nOutput : 0 \n\nExplanation :\n\n1st row     0\n2nd row     01\n3rd row     0110\n4th row     01101001\n5th row     0110100110010110\n\nTherefore, 0 is the 13th bit in the 5th row<\/code><\/pre>\n
<\/strong><\/u><\/a><\/p>\n
Can we use Recursion<\/code> here ?<\/em><\/strong>  <\/p>\n
\n
Yes<\/strong>, We see a pattern that is generated over here in each iteration so Recursion<\/code> can used.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. The idea is to use Binary Search<\/code>.   <\/li>\n
  2. First, check If the value of N<\/code> and I<\/code> are both equal to 1<\/code>, if Yes<\/code> return 0<\/code>.<\/li>\n
  3. Else recursively check the value of I<\/code> in (1 to 2N-1<\/sup>) positions as Nth<\/sup> row contains  2N-1<\/sup> values. Also maintain a flag<\/code> variable for the current value.<\/li>\n
  4. Calculate mid<\/code> value of the interval i.e. mid = (low + high)\/2<\/code><\/li>\n
  5. Check if low<\/code> becomes equal to high<\/code>, return current value i.e. flag<\/code><\/li>\n
  6. Else if I<\/code> is greater than mid<\/code>, then I<\/code> can only lie in the right subarray. So we recur for the right half. Also toggle the value of flag<\/code>.<\/li>\n
  7. Else (I<\/code> is less than mid<\/code>) recur in the left half with the same value of flag<\/code>.<\/li>\n
  8. Time Complexity<\/code> of this solution will be logarithmic<\/code> as Binary Search<\/code> is used.<\/li>\n<\/ol>\n<\/blockquote>\n
    ALGORITHM:<\/h3>\n
    if N = 1 and I = 1 \n    print 0\nelse \n    print solve(1, 2^(n-1), 0, I)\n\nsolve(low, high, flag, I) \n\n    mid = (low + high) \/ 2\n\n    if (low = high)\n        return flag\n\n    else if(I < mid)\n        return solve(low, mid, flag, I)\n\n    else \n        return solve(mid+1, high, flag, I)\n<\/code><\/pre>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t