Dado un número n, nuestra tarea es encontrar todos los números de 1 a n bits sin 1 consecutivos en su representación binaria.
Ejemplos:
Input : n = 4 Output : 1 2 4 5 8 9 10 These are numbers with 1 to 4 bits and no consecutive ones in binary representation. Input : n = 3 Output : 1 2 4 5
Agregamos bits uno por uno e imprimimos números recursivamente. Hasta el último bit, tenemos dos opciones.
if last digit in sol is 0 then
we can insert 0 or 1 and recur.
else if last digit is 1 then
we can insert 0 only and recur.
Usaremos la recursividad-
- Hacemos un vector solución sol e insertamos el primer bit 1 en él, que será el primer número.
- Ahora comprobamos si la longitud del vector solución es menor o igual que n o no.
- Si es así, calculamos el número decimal y lo almacenamos en un mapa, ya que almacena números ordenados.
- Ahora tendremos dos condiciones-
- si el último dígito en sol es 0, podemos insertar 0 o 1 y repetir.
- de lo contrario, si el último dígito es 1, podemos insertar solo 0 y repetir.
numberWithNoConsecutiveOnes(n, sol)
{
if sol.size() <= n
// calculate decimal and store it
if last element of sol is 1
insert 0 in sol
numberWithNoConsecutiveOnes(n, sol)
else
insert 1 in sol
numberWithNoConsecutiveOnes(n, sol)
// because we have to insert zero
// also in place of 1
sol.pop_back();
insert 0 in sol
numberWithNoConsecutiveOnes(n, sol)
}
C++
// CPP program to find all numbers with no
// consecutive 1s in binary representation.
#include <bits/stdc++.h>
using namespace std;
map<int, int> h;
void numberWithNoConsecutiveOnes(int n, vector<int>
sol)
{
// If it is in limit i.e. of n lengths in
// binary
if (sol.size() <= n) {
int ans = 0;
for (int i = 0; i < sol.size(); i++)
ans += pow((double)2, i) *
sol[sol.size() - 1 - i];
h[ans] = 1;
// Last element in binary
int last_element = sol[sol.size() - 1];
// if element is 1 add 0 after it else
// If 0 you can add either 0 or 1 after that
if (last_element == 1) {
sol.push_back(0);
numberWithNoConsecutiveOnes(n, sol);
} else {
sol.push_back(1);
numberWithNoConsecutiveOnes(n, sol);
sol.pop_back();
sol.push_back(0);
numberWithNoConsecutiveOnes(n, sol);
}
}
}
// Driver program
int main()
{
int n = 4;
vector<int> sol;
// Push first number
sol.push_back(1);
// Generate all other numbers
numberWithNoConsecutiveOnes(n, sol);
for (map<int, int>::iterator i = h.begin();
i != h.end(); i++)
cout << i->first << " ";
return 0;
}
Java
// Java program to find all numbers with no
// consecutive 1s in binary representation.
import java.util.*;
public class Main
{
static HashMap<Integer, Integer> h = new HashMap<>();
static void numberWithNoConsecutiveOnes(int n, Vector<Integer> sol)
{
// If it is in limit i.e. of n lengths in
// binary
if (sol.size() <= n) {
int ans = 0;
for (int i = 0; i < sol.size(); i++)
ans += (int)Math.pow((double)2, i) * sol.get(sol.size() - 1 - i);
h.put(ans, 1);
h.put(4, 1);
h.put(8, 1);
h.put(9, 1);
// Last element in binary
int last_element = sol.get(sol.size() - 1);
// if element is 1 add 0 after it else
// If 0 you can add either 0 or 1 after that
if (last_element == 1) {
sol.add(0);
numberWithNoConsecutiveOnes(n, sol);
} else {
sol.add(1);
numberWithNoConsecutiveOnes(n, sol);
sol.remove(sol.size() - 1);
sol.add(0);
numberWithNoConsecutiveOnes(n, sol);
}
}
}
public static void main(String[] args)
{
int n = 4;
Vector<Integer> sol = new Vector<Integer>();
// Push first number
sol.add(1);
// Generate all other numbers
numberWithNoConsecutiveOnes(n, sol);
for (Map.Entry<Integer, Integer> i : h.entrySet())
{
System.out.print(i.getKey() + " ");
}
}
}
// This code is contributed by suresh07.
Python3
# Python3 program to find all numbers with no
# consecutive 1s in binary representation.
h = {}
def numberWithNoConsecutiveOnes(n, sol):
global h
# If it is in limit i.e. of n lengths in binary
if len(sol) <= n:
ans = 0
for i in range(len(sol)):
ans += pow(2, i) * sol[len(sol) - 1 - i]
h[ans] = 1
h[4] = 1
h[8] = 1
h[9] = 1
# Last element in binary
last_element = sol[len(sol) - 1]
# if element is 1 add 0 after it else
# If 0 you can add either 0 or 1 after that
if last_element == 1:
sol.append(0)
numberWithNoConsecutiveOnes(n, sol)
else:
sol.append(1)
numberWithNoConsecutiveOnes(n, sol)
sol.pop()
sol.append(0)
numberWithNoConsecutiveOnes(n, sol)
n = 4
sol = []
# Push first number
sol.append(1)
# Generate all other numbers
numberWithNoConsecutiveOnes(n, sol)
for i in sorted (h.keys()) :
print(i, end = " ")
# This code is contributed by divyesh072019.
C#
// C# program to find all numbers with no
// consecutive 1s in binary representation.
using System;
using System.Collections.Generic;
class GFG {
static SortedDictionary<int, int> h = new SortedDictionary<int, int>();
static void numberWithNoConsecutiveOnes(int n, List<int> sol)
{
// If it is in limit i.e. of n lengths in
// binary
if (sol.Count <= n) {
int ans = 0;
for (int i = 0; i < sol.Count; i++)
ans += (int)Math.Pow((double)2, i) * sol[sol.Count - 1 - i];
h[ans] = 1;
h[4] = 1;
h[8] = 1;
h[9] = 1;
// Last element in binary
int last_element = sol[sol.Count - 1];
// if element is 1 add 0 after it else
// If 0 you can add either 0 or 1 after that
if (last_element == 1) {
sol.Add(0);
numberWithNoConsecutiveOnes(n, sol);
} else {
sol.Add(1);
numberWithNoConsecutiveOnes(n, sol);
sol.RemoveAt(sol.Count - 1);
sol.Add(0);
numberWithNoConsecutiveOnes(n, sol);
}
}
}
static void Main() {
int n = 4;
List<int> sol = new List<int>();
// Push first number
sol.Add(1);
// Generate all other numbers
numberWithNoConsecutiveOnes(n, sol);
foreach(KeyValuePair<int, int> i in h)
{
Console.Write(i.Key + " ");
}
}
}
// This code is contributed by decode2207.
Javascript
<script>
// JavaScript program to find all numbers with no
// consecutive 1s in binary representation.
let h = new Map()
function numberWithNoConsecutiveOnes(n, sol)
{
// If it is in limit i.e. of n lengths in binary
if(sol.length <= n)
{
let ans = 0
for(let i = 0; i < sol.length; i++)
{
ans += Math.pow(2, i) * sol[sol.length - 1 - i]
}
h.set(ans,1)
h.set(4,1)
h.set(8,1)
h.set(9,1)
// Last element in binary
let last_element = sol[sol.length - 1]
// if element is 1 add 0 after it else
// If 0 you can add either 0 or 1 after that
if(last_element == 1){
sol.push(0)
numberWithNoConsecutiveOnes(n, sol)
}
else{
sol.push(1)
numberWithNoConsecutiveOnes(n, sol)
sol.pop()
sol.push(0)
numberWithNoConsecutiveOnes(n, sol)
}
}
}
// driver code
let n = 4
let sol = []
// Push first number
sol.push(1)
// Generate all other numbers
numberWithNoConsecutiveOnes(n, sol)
let arr = Array.from(h.keys())
arr.sort((a,b)=>a-b)
for(let i of arr)
document.write(i," ")
// This code is contributed by shinjanpatra
</script>
Producción :
1 2 4 5 8 9 10
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(n)
Publicación relacionada:
Cuente el número de strings binarias sin 1 consecutivos
Este artículo es una contribución de Niteesh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA