Dados dos números enteros N y M , la tarea es encontrar la M- ésima string binaria lexicográficamente más pequeña (tiene solo los caracteres 1 y 0) de longitud N donde no puede haber dos 1 consecutivos.
Ejemplos:
Entrada: N = 2, M = 3.
Salida: 10
Explicación: Las únicas strings que se pueden hacer de tamaño 2 son [“00”, “01”, “10”] y la tercera string es “10”.Entrada: N = 3, M = 2.
Salida: 001
Enfoque: El problema se puede resolver con base en el siguiente enfoque:
Forme todas las strings de tamaño N y encuentre la M- ésima más pequeña entre ellas.
Siga los pasos mencionados a continuación para implementar la idea.
- Para cada carácter, hay dos opciones:
- Haz el caracter 0 .
- Si el último carácter de la string formada hasta ahora no es 1 , entonces el carácter actual también puede ser 1 .
- Para implementar este uso recursividad .
- Como el objetivo es encontrar el Mth más pequeño, para cualquier carácter llame a la función recursiva para 0 primero y para 1 después de eso (si se puede usar 1).
- Cada vez que se forma una string de longitud N , aumenta el número de strings.
- Si count = M , esa string es la M-ésima string lexicográficamente más pequeña requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Declared 2 global variable // one is the answer string and // the other is the count of created string string ans = ""; int Count = 0; // Function to find the mth string. void findString(int idx, int n, int m, string curr) { // When size of string is equal to n if (idx == n) { // If count of strings created // is equal to m-1 if (Count == m - 1) { ans = curr; } else { Count += 1; } return; } // Call the function to recurse for // currentstring + "0" curr += "0"; findString(idx + 1, n, m, curr); curr.pop_back(); // If the last character of curr is not 1 // then similarly recurse for "1". if (curr[curr.length() - 1] != '1') { curr += "1"; findString(idx + 1, n, m, curr); curr.pop_back(); } } // Driver Code int main() { int N = 2, M = 3; // Function call findString(0, N, M, ""); cout << ans << endl; return 0; }
Java
// Java code to implement the approach import java.io.*; class GFG { // Declared 2 global variable // one is the answer string and // the other is the count of created string static String ans = ""; public static int Count = 0; // Function to find the mth string. public static void findString(int idx, int n, int m, String curr) { // When size of string is equal to n if (idx == n) { // If count of strings created // is equal to m-1 if (Count == m - 1) { ans = curr; } else { Count += 1; } return; } // Call the function to recurse for // currentstring + "0" curr += "0"; findString(idx + 1, n, m, curr); curr=curr.substring(0,curr.length()-1); // If the last character of curr is not 1 // then similarly recurse for "1". if (curr.length()==0|| curr.charAt(curr.length() - 1) != '1') { curr += "1"; findString(idx + 1, n, m, curr); curr=curr.substring(0,curr.length()-1); } } // Driver Code public static void main(String[] args) { int N = 2, M = 3; // Function call findString(0, N, M, ""); System.out.println(ans); } } // This code is contributed by jana_sayantan.
Python3
# Python code to implement the approach # Declared 2 global variable # one is the answer string and # the other is the count of created string ans = "" Count = 0 # Function to find the mth string. def findString(idx, n, m, curr): global ans,Count # When size of string is equal to n if (idx == n): # If count of strings created # is equal to m-1 if (Count == m - 1): ans = curr else: Count += 1 return # Call the function to recurse for # currentstring + "0" curr += "0" findString(idx + 1, n, m, curr) curr = curr[0:len(curr) - 1] # If the last character of curr is not 1 # then similarly recurse for "1". if (len(curr) == 0 or curr[len(curr) - 1] != '1'): curr += "1" findString(idx + 1, n, m, curr) curr = curr[0:len(curr) - 1] # Driver Code N,M = 2,3 # Function call findString(0, N, M, "") print(ans) # This code is contributed by shinjanpatra
Javascript
<script> // JavaScript code to implement the approach // Declared 2 global variable // one is the answer string and // the other is the count of created string let ans = "" let Count = 0 // Function to find the mth string. function findString(idx, n, m, curr){ // When size of string is equal to n if (idx == n){ // If count of strings created // is equal to m-1 if (Count == m - 1) ans = curr else Count += 1 return } // Call the function to recurse for // currentstring + "0" curr += "0" findString(idx + 1, n, m, curr) curr = curr.substring(0,curr.length - 1) // If the last character of curr is not 1 // then similarly recurse for "1". if (curr.length == 0 || curr[curr.length - 1] != '1'){ curr += "1" findString(idx + 1, n, m, curr) curr = curr.substring(0,curr.length - 1) } } // Driver Code let N = 2,M = 3 // Function call findString(0, N, M, "") document.write(ans) // This code is contributed by shinjanpatra </script>
C#
// C# code for the above approach using System; using System.Collections.Generic; class GFG { // Declared 2 global variable // one is the answer string and // the other is the count of created string static String ans = ""; public static int Count = 0; // Function to find the mth string. public static void findString(int idx, int n, int m, string curr) { // When size of string is equal to n if (idx == n) { // If count of strings created // is equal to m-1 if (Count == m - 1) { ans = curr; } else { Count += 1; } return; } // Call the function to recurse for // currentstring + "0" curr += "0"; findString(idx + 1, n, m, curr); curr=curr.Substring(0,curr.Length-1); // If the last character of curr is not 1 // then similarly recurse for "1". if (curr.Length==0|| curr[(curr.Length - 1)] != '1') { curr += "1"; findString(idx + 1, n, m, curr); curr=curr.Substring(0,curr.Length-1); } } // Driver Code public static void Main() { int N = 2, M = 3; // Function call findString(0, N, M, ""); Console.WriteLine(ans); } }
10
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prathamjha5683 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA