Mth bit in Nth binary string from a sequence generated by the given operations | Python3 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
maxN = 10 NEW_LINE def calculateFib ( fib , n ) : NEW_LINE INDENT fib [ 0 ] = fib [ 1 ] = 1 NEW_LINE for x in range ( 2 , n ) : NEW_LINE INDENT fib [ x ] = ( fib [ x - 1 ] + fib [ x - 2 ] ) NEW_LINE DEDENT DEDENT def find_mth_bit ( n , m , fib ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return n NEW_LINE DEDENT len_left = fib [ n - 2 ] NEW_LINE len_right = fib [ n - 1 ] NEW_LINE if ( m <= len_left ) : NEW_LINE INDENT return find_mth_bit ( n - 2 , len_left + 1 - m , fib ) NEW_LINE DEDENT else : NEW_LINE INDENT return find_mth_bit ( n - 1 , len_right + 1 - ( m - len_left ) , fib ) NEW_LINE DEDENT DEDENT def find_mth_bitUtil ( n , m ) : NEW_LINE INDENT fib = [ 0 for i in range ( maxN ) ] NEW_LINE calculateFib ( fib , maxN ) NEW_LINE ans = find_mth_bit ( n , m , fib ) NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 NEW_LINE m = 3 NEW_LINE find_mth_bitUtil ( n , m ) NEW_LINE DEDENT