Mth bit en Nth string binaria de una secuencia generada por las operaciones dadas

Dados dos números enteros N y M , genere una secuencia de N strings binarias mediante los siguientes pasos:

• S ₀ = “0”
• S1 = “1 _”
• Genere las strings restantes mediante la ecuación S _i = reverse(S _{i – 2} ) + reverse(S _{i – 1} )

La tarea es encontrar el M ^-ésimo bit establecido en la N ^-ésima string.

Ejemplos:

Entrada: N = 4, M = 3
Salida: 0
Explicación:
S ₀ =”0″
S ₁ =”1″
S ₂ =”01″
S ₃ =”110″
S ₄ =”10011″
Por lo tanto, el _3er bit en S ₄ es ‘0’

Entrada: N = 5, M = 2
Salida: 1

Enfoque ingenuo: El enfoque más simple es generar S ₂ a S _{N – 1} y atravesar la string S _{N – 1} para encontrar el M ^-ésimo bit. 

Complejidad temporal: O(N * 2 ^N) Espacio auxiliar: O(N) 

Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:

• Calcule y almacene los primeros N números de Fibonacci en una array, digamos fib[]
• Ahora, busque el M ^-ésimo bit en la N ^-ésima string.
• Si N > 1 : Considerando que S _N es la concatenación del reverso de la string S _{N – 2} y el reverso de la string S _{N – 1} , la longitud de la string S _{N – 2} es igual a fib[N – 2] y la longitud de la string S _{N – 1} es igual a fib[N – 1] . 
  • Si M ≤ fib[n-2]: Significa que M se encuentra en S _{N – 2} , por lo tanto, busque recursivamente el (fib[N – 2] + 1 – M) ^th bit de la string S _{N – 2} .
  • Si M > fib[N – 2]: Significa que M se encuentra en S _{N – 1} , por lo tanto, busca recursivamente el (fib[N – 1]+ 1 – (M – fib[N – 2])) el bit ^th de S _{N – 1} .
• Si N ≤ 1: devuelve N .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
#define maxN 10
 
// Function to calculate N
// Fibonacci numbers
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 Sn
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);
    }
}
 
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 Code
int main()
{
 
    int n = 5, m = 3;
    find_mth_bitUtil(n, m);
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
static final int maxN = 10;
 
// Function to calculate N
// Fibonacci numbers
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];
  }
}
 
// Function to find the mth bit
// in the String Sn
static 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 Code
public static void main(String[] args)
{
  int n = 5, m = 3;
  find_mth_bitUtil(n, m);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for above approach
maxN = 10
 
# Function to calculate N
# Fibonacci numbers
def 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 Sn
def 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 Code
if __name__ == '__main__':
 
    n = 5
    m = 3
     
    find_mth_bitUtil(n, m)
 
# This code is contributed by mohit kumar 29

// C# program for
// the above approach
using System;
class GFG{
 
static int maxN = 10;
 
// Function to calculate N
// Fibonacci numbers
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];
  }
}
 
// Function to find the mth bit
// in the String Sn
static 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 Code
public static void Main()
{
  int n = 5, m = 3;
  find_mth_bitUtil(n, m);
}
}
 
// This code is contributed by Chitranayal

<script>
// JavaScript program for above approach
 
const maxN = 10
 
// Function to calculate N
// Fibonacci numbers
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 to find the mth bit
// in the string Sn
function 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>

1

Complejidad temporal: O(N)
Espacio auxiliar: O(N)