Given two integers N and M, generate a sequence of N binary strings by the following steps:
- S0 = “0”
- S1 = “1”
- Generate remaining strings by the equation Si = reverse(Si – 2) + reverse(Si – 1)
The task is to find the Mth set bit in the Nth string.
Examples:
Input: N = 4, M = 3
Output: 0
Explanation:
S0 =”0″
S1 =”1″
S2 =”01″
S3 =”110″
S4 =”10011″
Therefore, the 3rd bit in S4 is ‘0’Input: N = 5, M = 2
Output: 1
Naive Approach: The simplest approach is to generate S2 to SN – 1 and traverse the string SN – 1 to find the Mth bit.
Time Complexity: O(N * 2N)
Auxiliary Space: O(N)
Efficient Approach: Follow the steps below to optimize the above approach:
- Compute and store the first N Fibonacci numbers in an array, say fib[]
- Now, search for the Mth bit in the Nth string.
- If N > 1 : Considering SN to be the concatenation of reverse of string SN – 2 and reverse of string SN – 1, the length of the string SN – 2 is equal to fib[N – 2] and length of the string SN – 1 is equal to fib[N – 1].
- If M ? fib[n-2]: It signifies that M lies in SN – 2, therefore, recursively search for the (fib[N – 2] + 1 – M)th bit of the string SN – 2.
- If M > fib[N – 2]: It signifies that M lies in SN – 1, therefore, recursively search for the (fib[N – 1]+ 1 – (M – fib[N – 2]))th bit of SN – 1.
- If N ? 1: return N.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;#define maxN 10// Function to calculate N// Fibonacci numbersvoid 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]; }}// Function to find the mth bit// in the string Snint find_mth_bit(int n, int m, int fib[]){ // Base case if (n <= 1) { return n; } // Length of left half int len_left = fib[n - 2]; // Length of the right half int len_right = fib[n - 1]; if (m <= len_left) { // Recursive check in the left half return find_mth_bit(n - 2, len_left + 1 - m, fib); } else { // Recursive check in the right half return find_mth_bit( n - 1, len_right + 1 - (m - len_left), fib); }}void find_mth_bitUtil(int n, int m){ int fib[maxN]; calculateFib(fib, maxN); int ans = find_mth_bit(n, m, fib); cout << ans << ' ';}// Driver Codeint main(){ int n = 5, m = 3; find_mth_bitUtil(n, m); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{static final int maxN = 10;// Function to calculate N// Fibonacci numbersstatic 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]; }}// Function to find the mth bit// in the String Snstatic int find_mth_bit(int n, int m, int fib[]){ // Base case if (n <= 1) { return n; } // Length of left half int len_left = fib[n - 2]; // Length of the right half int len_right = fib[n - 1]; if (m <= len_left) { // Recursive check in // the left half return find_mth_bit(n - 2, len_left + 1 - m, fib); } else { // Recursive check in // the right half 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 + " ");}// Driver Codepublic static void main(String[] args){ int n = 5, m = 3; find_mth_bitUtil(n, m);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for above approachmaxN = 10# Function to calculate N# Fibonacci numbersdef calculateFib(fib, n): fib[0] = fib[1] = 1 for x in range(2, n): fib[x] = (fib[x - 1] + fib[x - 2])# Function to find the mth bit# in the string Sndef find_mth_bit(n, m, fib): # Base case if (n <= 1): return n # Length of left half len_left = fib[n - 2] # Length of the right half len_right = fib[n - 1] if (m <= len_left): # Recursive check in the left half return find_mth_bit(n - 2, len_left + 1 - m, fib) else: # Recursive check in the right half return find_mth_bit(n - 1, len_right + 1 - (m - len_left), fib)def find_mth_bitUtil(n, m): fib = [0 for i in range(maxN)] calculateFib(fib, maxN) ans = find_mth_bit(n, m, fib) print(ans)# Driver Codeif __name__ == '__main__': n = 5 m = 3 find_mth_bitUtil(n, m)# This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approachusing System;class GFG{static int maxN = 10;// Function to calculate N// Fibonacci numbersstatic 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]; }}// Function to find the mth bit// in the String Snstatic int find_mth_bit(int n, int m, int []fib){ // Base case if (n <= 1) { return n; } // Length of left half int len_left = fib[n - 2]; // Length of the right half int len_right = fib[n - 1]; if (m <= len_left) { // Recursive check in // the left half return find_mth_bit(n - 2, len_left + 1 - m, fib); } else { // Recursive check in // the right half 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); Console.Write(ans + " ");}// Driver Codepublic static void Main(){ int n = 5, m = 3; find_mth_bitUtil(n, m);}}// This code is contributed by Chitranayal |
Javascript
<script>// JavaScript program for above approachconst maxN = 10// Function to calculate N// Fibonacci numbersfunction calculateFib(fib, n){ fib[0] = fib[1] = 1; for (let x = 2; x < n; x++) { fib[x] = fib[x - 1] + fib[x - 2]; }}// Function to find the mth bit// in the string Snfunction find_mth_bit(n, m, fib){ // Base case if (n <= 1) { return n; } // Length of left half let len_left = fib[n - 2]; // Length of the right half let len_right = fib[n - 1]; if (m <= len_left) { // Recursive check in the left half return find_mth_bit(n - 2, len_left + 1 - m, fib); } else { // Recursive check in the right half 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 + " ");}// Driver Code let n = 5, m = 3; find_mth_bitUtil(n, m);// This code is contributed by Surbhi Tyagi.</script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
