Mth bit in Nth binary string from a sequence generated by the given operations | JavaScript program for above approach ; Function to calculate N Fibonacci numbers ; Function to find the mth bit in the string Sn ; Base case ; Length of left half ; Length of the right half ; Recursive check in the left half ; Recursive check in the right half ; Driver Code
const maxN = 10 function calculateFib ( fib , n ) { fib [ 0 ] = fib [ 1 ] = 1 ; for ( let x = 2 ; x < n ; x ++ ) { fib [ x ] = fib [ x - 1 ] + fib [ x - 2 ] ; } } function find_mth_bit ( n , m , fib ) { if ( n <= 1 ) { return n ; } let len_left = fib [ n - 2 ] ; let len_right = fib [ n - 1 ] ; if ( m <= len_left ) { return find_mth_bit ( n - 2 , len_left + 1 - m , fib ) ; } else { return find_mth_bit ( n - 1 , len_right + 1 - ( m - len_left ) , fib ) ; } } function find_mth_bitUtil ( n , m ) { let fib = new Array ( maxN ) ; calculateFib ( fib , maxN ) ; let ans = find_mth_bit ( n , m , fib ) ; document . write ( ans + " " ) ; } let n = 5 , m = 3 ; find_mth_bitUtil ( n , m ) ;