Dado un número N , la tarea es verificar si la representación binaria del número N tiene solo «01» y «10» como substring o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: N = 5
Salida: Sí
Explicación:
(5) 10 es (101) 2 que contiene solo «01» y «10» como substring.
Entrada: N = 11
Salida: No
Explicación:
(11) 10 es (1011) 2 que contiene solo «11» una substring.
Enfoque: El problema dado se puede resolver usando las siguientes observaciones:
- Dado que la substring debe contener «01» y «10» . Por lo tanto, la representación binaria contiene 1 y 0 alternativamente.
- Para representaciones binarias que contienen 0 y 1 alternativamente, se puede observar el siguiente patrón:
2, 5, 10, 21, …
- El patrón anterior es de la forma 2 * x y (4 * x + 1) tal que el último término de la serie es x .
De la observación anterior, la idea es generar la serie dada usando el patrón anterior y verificar si el número dado existe en el patrón o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
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;
vector<int> Ans;
// Function to generate all numbers
// having "01" and "10" as a substring
void populateNumber()
{
// Insert 2 and 5
Ans.push_back(2);
Ans.push_back(5);
long long int x = 5;
// Iterate till x is 10 ^ 15
while (x < 1000000000001) {
// Multiply x by 2
x *= 2;
Ans.push_back(x);
// Update x as x*2 + 1
x = x * 2 + 1;
Ans.push_back(x);
}
}
// Function to check if binary representation
// of N contains only "01" and "10" as substring
string checkString(long long int N)
{
// Function Call to generate all
// such numbers
populateNumber();
// Check if a number N
// exists in Ans[] or not
for (auto& it : Ans) {
// If the number exists
if (it == N) {
return "Yes";
}
}
// Otherwise
return "No";
}
// Driver Code
int main()
{
long long int N = 5;
// Function Call
cout << checkString(N);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG
{
static int N = 200000;
static long Ans[] = new long [200000];
static int index = 0;
// Function to generate all numbers
// having "01" and "10" as a substring
static void populateNumber()
{
// Insert 2 and 5
Ans[index++] = (2);
Ans[index++] = (5);
long x = 5;
long inf = 1000000000001L;
// Iterate till x is 10 ^ 15
while (x < inf)
{
// Multiply x by 2
x *= 2;
Ans[index++] = (x);
// Update x as x*2 + 1
x = x * 2 + 1;
Ans[index++] = (x);
}
}
// Function to check if binary representation
// of N contains only "01" and "10" as substring
static void checkString(int N)
{
// Function Call to generate all
// such numbers
populateNumber();
// Check if a number N
// exists in Ans[] or not
for (int i = 0; i < index; i++)
{
// If the number exists
if (Ans[i] == N)
{
System.out.println("YES");
return;
}
}
System.out.println("NO");
}
// Driver Code
public static void main(String[] args)
{
N = 5;
checkString(N);
}
}
// This code is contributed by amreshkumar3.
Python3
# Python3 program to implement # the above approach Ans = [] # Function to generate all numbers # having "01" and "10" as a substring def populateNumber() : # Insert 2 and 5 Ans.append(2) Ans.append(5) x = 5 # Iterate till x is 10 ^ 15 while (x < 1000000000001) : # Multiply x by 2 x *= 2 Ans.append(x) # Update x as x*2 + 1 x = x * 2 + 1 Ans.append(x) # Function to check if binary representation # of N contains only "01" and "10" as substring def checkString(N) : # Function Call to generate all # such numbers populateNumber() # Check if a number N # exists in Ans[] or not for it in Ans : # If the number exists if (it == N) : return "Yes" # Otherwise return "No" # Driver Code N = 5 # Function Call print(checkString(N)) # This code is contributed by sanjoy_62
C#
// C# Program to implement
// the above approach
using System;
class GFG
{
static int N = 200000;
static long []Ans = new long [200000];
static int index = 0;
// Function to generate all numbers
// having "01" and "10" as a substring
static void populateNumber()
{
// Insert 2 and 5
Ans[index++] = (2);
Ans[index++] = (5);
long x = 5;
long inf = 1000000000001L;
// Iterate till x is 10 ^ 15
while (x < inf)
{
// Multiply x by 2
x *= 2;
Ans[index++] = (x);
// Update x as x*2 + 1
x = x * 2 + 1;
Ans[index++] = (x);
}
}
// Function to check if binary representation
// of N contains only "01" and "10" as substring
static void checkString(int N)
{
// Function Call to generate all
// such numbers
populateNumber();
// Check if a number N
// exists in Ans[] or not
for (int i = 0; i < index; i++)
{
// If the number exists
if (Ans[i] == N)
{
Console.WriteLine("YES");
return;
}
}
Console.WriteLine("NO");
}
// Driver Code
public static void Main(String[] args)
{
N = 5;
checkString(N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript Program to implement
// the above approach
var N = 200000;
var Ans = Array.from({length: N}, (_, i) => 0);
var index = 0;
// Function to generate all numbers
// having "01" and "10" as a substring
function populateNumber()
{
// Insert 2 and 5
Ans[index++] = (2);
Ans[index++] = (5);
var x = 5;
var inf = 1000000000001;
// Iterate till x is 10 ^ 15
while (x < inf)
{
// Multiply x by 2
x *= 2;
Ans[index++] = (x);
// Update x as x*2 + 1
x = x * 2 + 1;
Ans[index++] = (x);
}
}
// Function to check if binary representation
// of N contains only "01" and "10" as substring
function checkString(N)
{
// Function Call to generate all
// such numbers
populateNumber();
// Check if a number N
// exists in Ans or not
for (i = 0; i < index; i++)
{
// If the number exists
if (Ans[i] == N)
{
document.write("YES");
return;
}
}
document.write("NO");
}
// Driver Code
N = 5;
checkString(N);
// This code contributed by shikhasingrajput
</script>
Producción:
Yes
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)