Mth bit in Nth binary string from a sequence generated by the given operations | Java program for the 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
import java . util . * ; class GFG { static final int maxN = 10 ; static void calculateFib ( int fib [ ] , int n ) { fib [ 0 ] = fib [ 1 ] = 1 ; for ( int x = 2 ; x < n ; x ++ ) { fib [ x ] = fib [ x - 1 ] + fib [ x - 2 ] ; } } static int find_mth_bit ( int n , int m , int fib [ ] ) { if ( n <= 1 ) { return n ; } int len_left = fib [ n - 2 ] ; int 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 ) ; } } static void find_mth_bitUtil ( int n , int m ) { int [ ] fib = new int [ maxN ] ; calculateFib ( fib , maxN ) ; int ans = find_mth_bit ( n , m , fib ) ; System . out . print ( ans + " ▁ " ) ; } public static void main ( String [ ] args ) { int n = 5 , m = 3 ; find_mth_bitUtil ( n , m ) ; } }