Encuentre los primeros caracteres K en el término N de la secuencia Thue-Morse

Dados dos números enteros N y K , la tarea es imprimir los primeros K bits del término N de la secuencia de ^Thue-Morse . La secuencia de Thue-Morse es una secuencia binaria. Comienza con un «0» como su primer término. Y luego, el siguiente término se genera reemplazando «0» con «01» y «1» con «10».

Ejemplos:

Entrada: N = 3, K = 2
Salida: 01
Explicación: El primer término es «0».
El segundo término se obtiene reemplazando «0» con «01», es decir, el segundo término es «01».
El tercer término de la secuencia se obtiene reemplazando «0» por «01» y «1» por «10».
Entonces el tercer término se convierte en «0110». Por lo tanto, los 2 primeros caracteres del 3er término son «01».

Entrada: N = 4, K = 7
Salida: 0110100

Enfoque: El enfoque básico para resolver este problema es generar el N ^-ésimo término de la secuencia e imprimir los primeros K caracteres de ese término. Esto se puede hacer usando el algoritmo discutido aquí .

Complejidad de tiempo : O(N * 2 ^N )
Espacio auxiliar : O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar al observar que el término i es la concatenación de (i – 1) ^el término y el inverso de (i – 1) el término donde ^inverso significa cambiar la polaridad de todos los bits en un entero binario . Por lo tanto, el término x , A _i [x] = A _i-1 [x – 1] si ( x < 2 ^i-1 ), de lo contrario A _i [x] = !A _i-1 [x – 2 ^i-1 ] . Por lo tanto, usando esta relación, una función recursivase puede crear para calcular el valor de cada bit en el término ^N.

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

C++

#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find the
// value of the kth bit in Nth term
int findDig(int N, long K,  int curr)
{
   
  // Base Case
  if (N == 0) {
    return curr;
  }
 
  // Stores the middle index
  long middle = (long)pow(2, N) / 2;
 
  // If K lies in 1st part
  if (K <= middle) {
 
    // Recursive Call
    return findDig(N - 1, K, curr);
  }
 
  // If K lies in 2nd part
  // having inverted value
  else {
    if (curr == 0) {
      curr = 1;
    }
    else {
      curr = 0;
    }
 
    // Recursive Call
    return findDig(N - 1,
                   K - middle, curr);
  }
}
 
// Function to find first K characters
// in Nth term of Thue-Morse sequence
void firstKTerms(int N, int K)
{
   
  // Loop to iterate all K bits
  for (int i = 1; i <= K; ++i)
  {
 
    // Print value of ith bit
    cout << (findDig(N, i, 0));
  }
}
 
// Driver Code
int main() {
 
  int N = 4;
  int K = 7;
 
  firstKTerms(N, K);
  return 0;
}
 
// This code is contributed by hrithikgarg03188.

Java

// Java Implementation of the above approach
import java.io.*;
import java.util.*;
class GFG {
 
    // Recursive function to find the
    // value of the kth bit in Nth term
    public static int findDig(int N, long K,
                              int curr)
    {
        // Base Case
        if (N == 0) {
            return curr;
        }
 
        // Stores the middle index
        long middle = (long)Math.pow(2, N) / 2;
 
        // If K lies in 1st part
        if (K <= middle) {
 
            // Recursive Call
            return findDig(N - 1, K, curr);
        }
 
        // If K lies in 2nd part
        // having inverted value
        else {
            if (curr == 0) {
                curr = 1;
            }
            else {
                curr = 0;
            }
 
            // Recursive Call
            return findDig(N - 1,
                           K - middle, curr);
        }
    }
 
    // Function to find first K characters
    // in Nth term of Thue-Morse sequence
    public static void firstKTerms(int N, int K)
    {
        // Loop to iterate all K bits
        for (int i = 1; i <= K; ++i) {
 
            // Print value of ith bit
            System.out.print(findDig(N, i, 0));
        }
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int N = 4;
        int K = 7;
 
        firstKTerms(N, K);
    }
}

Python3

# Recursive function to find the
# value of the kth bit in Nth term
def findDig(N, K, curr):
 
    # Base Case
    if (N == 0):
        return curr
 
    # Stores the middle index
    middle = pow(2, N) // 2
 
    # If K lies in 1st part
    if (K <= middle):
 
        # Recursive Call
        return findDig(N - 1, K, curr)
 
    # If K lies in 2nd part
    # having inverted value
    else:
        if (curr == 0):
            curr = 1
 
        else:
            curr = 0
 
        # Recursive Call
        return findDig(N - 1, K - middle, curr)
 
# Function to find first K characters
# in Nth term of Thue-Morse sequence
def firstKTerms(N, K):
 
    # Loop to iterate all K bits
    for i in range(1, K+1):
 
     # Print value of ith bit
        print(findDig(N, i, 0), end="")
 
# Driver Code
if __name__ == "__main__":
 
    N = 4
    K = 7
 
    firstKTerms(N, K)
 
    # This code is contributed by rakeshsahni

C#

// C# Implementation of the above approach
using System;
class GFG
{
 
  // Recursive function to find the
  // value of the kth bit in Nth term
  public static int findDig(int N, long K, int curr)
  {
     
    // Base Case
    if (N == 0)
    {
      return curr;
    }
 
    // Stores the middle index
    long middle = (long)Math.Pow(2, N) / 2;
 
    // If K lies in 1st part
    if (K <= middle)
    {
 
      // Recursive Call
      return findDig(N - 1, K, curr);
    }
 
    // If K lies in 2nd part
    // having inverted value
    else
    {
      if (curr == 0)
      {
        curr = 1;
      }
      else
      {
        curr = 0;
      }
 
      // Recursive Call
      return findDig(N - 1,
                     K - middle, curr);
    }
  }
 
  // Function to find first K characters
  // in Nth term of Thue-Morse sequence
  public static void firstKTerms(int N, int K)
  {
     
    // Loop to iterate all K bits
    for (int i = 1; i <= K; ++i)
    {
 
      // Print value of ith bit
      Console.Write(findDig(N, i, 0));
    }
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 4;
    int K = 7;
 
    firstKTerms(N, K);
  }
}
 
// This code is contributed by saurabh_jaiswal.

Javascript

<script>
       // JavaScript code for the above approach
 
       // Recursive function to find the
       // value of the kth bit in Nth term
       function findDig(N, K, curr)
       {
           // Base Case
           if (N == 0) {
               return curr;
           }
 
           // Stores the middle index
           let middle = Math.floor(Math.pow(2, N) / 2);
 
           // If K lies in 1st part
           if (K <= middle) {
 
               // Recursive Call
               return findDig(N - 1, K, curr);
           }
 
           // If K lies in 2nd part
           // having inverted value
           else {
               if (curr == 0) {
                   curr = 1;
               }
               else {
                   curr = 0;
               }
 
               // Recursive Call
               return findDig(N - 1,
                   K - middle, curr);
           }
       }
 
       // Function to find first K characters
       // in Nth term of Thue-Morse sequence
       function firstKTerms(N, K) {
           // Loop to iterate all K bits
           for (let i = 1; i <= K; ++i) {
 
               // Print value of ith bit
               document.write(findDig(N, i, 0));
           }
       }
 
       // Driver Code
       let N = 4;
       let K = 7;
 
       firstKTerms(N, K);
 
        // This code is contributed by Potta Lokesh
   </script>

Producción

Complejidad de tiempo : O(K*log N)
Espacio auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta