Dé una string binaria str y un entero N, la tarea es verificar si las substrings de la string contienen todas las representaciones binarias de enteros no negativos menores o iguales que el entero N dado.
Ejemplos:
Entrada: str = “0110″, N = 3
Salida: Verdadero
Explicación:
Dado que las substrings “0″, “1″, “10″ y “11″ pueden formarse a partir de una string dada. Por lo tanto, todas las representaciones binarias de 0 a 3 están presentes como substrings en una string binaria dada.Entrada: str = “0110”, N = 4
Salida: Falso
Explicación:
Dado que las substrings “0″, “1″, “10″ y “11″ pueden formarse a partir de una string dada, pero no “100”. Por lo tanto la respuesta es Falso
Enfoque:
el problema anterior se puede resolver utilizando BitSet y HashMap . Siga los pasos que se indican a continuación para resolver el problema.
- Inicialice un mapa [] para marcar las strings y tome una variable de conjunto de bits para convertir el número de decimal a binario.
- Tome una cuenta variable más como cero.
- ejecute el ciclo de N a 1 usando la variable i y verifique que los números correspondientes estén marcados en un mapa o no.
- si el número i no está marcado en un mapa [] , convierta el número actual en binario usando la variable de conjunto de bits ans.
- luego verifique si la string binaria convertida es una substring de la string dada o no.
- si no es una substring entonces
- ejecutar while loop a menos que no esté marcado y el número binario se convierta en cero
- marcar la i en un mapa
- incrementar el conteo
- hacer el desplazamiento a la derecha del número convertido. Esto se hace porque si cualquier string x se convierte en binario (por ejemplo, 111001 ) y esta substring ya está marcada en el mapa, entonces 11100 ya se marcará automáticamente.
Esto se basa en el hecho de que si i existe, i>>1 también existe.
- Finalmente verifique si cuenta? N + 1 , luego imprime Verdadero De lo
contrario imprime Falso
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to convert decimal to binary
// representation
string decimalToBinary(int N)
{
string ans = "";
// Iterate over all bits of N
while (N > 0) {
// If bit is 1
if (N & 1) {
ans = '1' + ans;
}
else {
ans = '0' + ans;
}
N /= 2;
}
// Return binary representation
return ans;
}
// Function to check if binary conversion
// of numbers from N to 1 exists in the
// string as a substring or not
string checkBinaryString(string& str, int N)
{
// To store the count of number
// exists as a substring
int map[N + 10], cnt = 0;
memset(map, 0, sizeof(map));
// Traverse from N to 1
for (int i = N; i > 0; i--) {
// If current number is not
// present in map
if (!map[i]) {
// Store current number
int t = i;
// Find binary of t
string s = decimalToBinary(t);
// If the string s is a
// substring of str
if (str.find(s) != str.npos) {
while (t && !map[t]) {
// Mark t as true
map[t] = 1;
// Increment the count
cnt++;
// Update for t/2
t >>= 1;
}
}
}
}
// Special judgement '0'
for (int i = 0; i < str.length(); i++) {
if (str[i] == '0') {
cnt++;
break;
}
}
// If the count is N+1, return "yes"
if (cnt == N + 1)
return "True";
else
return "False";
}
// Driver Code
int main()
{
// Given String
string str = "0110";
// Given Number
int N = 3;
// Function Call
cout << checkBinaryString(str, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to convert decimal to binary
// representation
static String decimalToBinary(int N)
{
String ans = "";
// Iterate over all bits of N
while (N > 0)
{
// If bit is 1
if (N % 2 == 1)
{
ans = '1' + ans;
}
else
{
ans = '0' + ans;
}
N /= 2;
}
// Return binary representation
return ans;
}
// Function to check if binary conversion
// of numbers from N to 1 exists in the
// String as a subString or not
static String checkBinaryString(String str, int N)
{
// To store the count of number
// exists as a subString
int []map = new int[N + 10];
int cnt = 0;
// Traverse from N to 1
for(int i = N; i > 0; i--)
{
// If current number is not
// present in map
if (map[i] == 0)
{
// Store current number
int t = i;
// Find binary of t
String s = decimalToBinary(t);
// If the String s is a
// subString of str
if (str.contains(s))
{
while (t > 0 && map[t] == 0)
{
// Mark t as true
map[t] = 1;
// Increment the count
cnt++;
// Update for t/2
t >>= 1;
}
}
}
}
// Special judgement '0'
for(int i = 0; i < str.length(); i++)
{
if (str.charAt(i) == '0')
{
cnt++;
break;
}
}
// If the count is N+1, return "yes"
if (cnt == N + 1)
return "True";
else
return "False";
}
// Driver Code
public static void main(String[] args)
{
// Given String
String str = "0110";
// Given number
int N = 3;
// Function call
System.out.print(checkBinaryString(str, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of # the above approach # Function to convert decimal to # binary representation def decimalToBinary(N): ans = "" # Iterate over all bits of N while(N > 0): # If bit is 1 if(N & 1): ans = '1' + ans else: ans = '0' + ans N //= 2 # Return binary representation return ans # Function to check if binary conversion # of numbers from N to 1 exists in the # string as a substring or not def checkBinaryString(str, N): # To store the count of number # exists as a substring map = [0] * (N + 10) cnt = 0 # Traverse from N to 1 for i in range(N, -1, -1): # If current number is not # present in map if(not map[i]): # Store current number t = i # Find binary of t s = decimalToBinary(t) # If the string s is a # substring of str if(s in str): while(t and not map[t]): # Mark t as true map[t] = 1 # Increment the count cnt += 1 # Update for t/2 t >>= 1 # Special judgement '0' for i in range(len(str)): if(str[i] == '0'): cnt += 1 break # If the count is N+1, return "yes" if(cnt == N + 1): return "True" else: return "False" # Driver Code if __name__ == '__main__': # Given String str = "0110" # Given Number N = 3 # Function Call print(checkBinaryString(str, N)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function to convert decimal to binary
// representation
static String decimalToBinary(int N)
{
String ans = "";
// Iterate over all bits of N
while (N > 0)
{
// If bit is 1
if (N % 2 == 1)
{
ans = '1' + ans;
}
else
{
ans = '0' + ans;
}
N /= 2;
}
// Return binary representation
return ans;
}
// Function to check if binary conversion
// of numbers from N to 1 exists in the
// String as a subString or not
static String checkBinaryString(String str, int N)
{
// To store the count of number
// exists as a subString
int []map = new int[N + 10];
int cnt = 0;
// Traverse from N to 1
for(int i = N; i > 0; i--)
{
// If current number is not
// present in map
if (map[i] == 0)
{
// Store current number
int t = i;
// Find binary of t
String s = decimalToBinary(t);
// If the String s is a
// subString of str
if (str.Contains(s))
{
while (t > 0 && map[t] == 0)
{
// Mark t as true
map[t] = 1;
// Increment the count
cnt++;
// Update for t/2
t >>= 1;
}
}
}
}
// Special judgement '0'
for(int i = 0; i < str.Length; i++)
{
if (str[i] == '0')
{
cnt++;
break;
}
}
// If the count is N+1, return "yes"
if (cnt == N + 1)
return "True";
else
return "False";
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String str = "0110";
// Given number
int N = 3;
// Function call
Console.Write(checkBinaryString(str, N));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program for the above approach
// Function to convert decimal to binary
// representation
function decimalToBinary(N)
{
var ans = "";
// Iterate over all bits of N
while (N > 0) {
// If bit is 1
if (N % 2 == 1){
ans = '1' + ans;
}
else {
ans = '0' + ans;
}
N = parseInt(N/2);
}
// Return binary representation
return ans;
}
// Function to check if binary conversion
// of numbers from N to 1 exists in the
// string as a substring or not
function checkBinaryString(str, N)
{
// To store the count of number
// exists as a substring
var map = Array(N+10).fill(0), cnt = 0;
// Traverse from N to 1
for (var i = N; i > 0; i--) {
// If current number is not
// present in map
if (!map[i]) {
// Store current number
var t = i;
// Find binary of t
var s = decimalToBinary(t);
// If the string s is a
// substring of str
if (str.includes(s)) {
while (t>0 && map[t] == 0) {
// Mark t as true
map[t] = 1;
// Increment the count
cnt++;
// Update for t/2
t >>= 1;
}
}
}
}
// Special judgement '0'
for (var i = 0; i < str.length; i++) {
if (str[i] == '0') {
cnt++;
break;
}
}
// If the count is N+1, return "yes"
if (cnt == N + 1)
return "True";
else
return "False";
}
// Driver Code
// Given String
var str = "0110";
// Given Number
var N = 3;
// Function Call
document.write( checkBinaryString(str, N));
</script>
Producción:
True
Complejidad de tiempo: O(N logN)
Espacio auxiliar: O(N), ya que el espacio adicional de tamaño N se usa para hacer una array