Dado un número n, imprima los primeros n enteros positivos con exactamente dos bits establecidos en su representación binaria.
Ejemplos:
Input: n = 3 Output: 3 5 6 The first 3 numbers with two set bits are 3 (0011), 5 (0101) and 6 (0110) Input: n = 5 Output: 3 5 6 9 10 12
Una solución simple es considerar todos los enteros positivos uno por uno a partir de 1. Para cada número, verifique si tiene exactamente dos conjuntos de bits. Si un número tiene exactamente dos bits establecidos, imprímalo e incremente el conteo de dichos números.
Una solución eficiente es generar directamente dichos números. Si observamos claramente los números, podemos reescribirlos como se indica a continuación pow(2,1)+pow(2,0), pow(2,2)+pow(2,0), pow(2,2)+pow (2,1), pow(2,3)+pow(2,0), pow(2,3)+pow(2,1), pow(2,3)+pow(2,2), …… …
Todos los números se pueden generar en orden creciente según el mayor de los dos bits establecidos. La idea es arreglar más de dos bits uno por uno. Para el bit establecido más alto actual, considere todos los bits más bajos e imprima los números formados.
C++
// C++ program to print first n numbers
// with exactly two set bits
#include <iostream>
using namespace std;
// Prints first n numbers with two set bits
void printTwoSetBitNums(int n)
{
// Initialize higher of two sets bits
int x = 1;
// Keep reducing n for every number
// with two set bits.
while (n > 0)
{
// Consider all lower set bits for
// current higher set bit
int y = 0;
while (y < x)
{
// Print current number
cout << (1 << x) + (1 << y) << " ";
// If we have found n numbers
n--;
if (n == 0)
return;
// Consider next lower bit for current
// higher bit.
y++;
}
// Increment higher set bit
x++;
}
}
// Driver code
int main()
{
printTwoSetBitNums(4);
return 0;
}
Java
// Java program to print first n numbers
// with exactly two set bits
import java.io.*;
class GFG
{
// Function to print first n numbers with two set bits
static void printTwoSetBitNums(int n)
{
// Initialize higher of two sets bits
int x = 1;
// Keep reducing n for every number
// with two set bits
while (n > 0)
{
// Consider all lower set bits for
// current higher set bit
int y = 0;
while (y < x)
{
// Print current number
System.out.print(((1 << x) + (1 << y)) +" ");
// If we have found n numbers
n--;
if (n == 0)
return;
// Consider next lower bit for current
// higher bit.
y++;
}
// Increment higher set bit
x++;
}
}
// Driver program
public static void main (String[] args)
{
int n = 4;
printTwoSetBitNums(n);
}
}
// This code is contributed by Pramod Kumar
Python3
# Python3 program to print first n # numbers with exactly two set bits # Prints first n numbers # with two set bits def printTwoSetBitNums(n) : # Initialize higher of # two sets bits x = 1 # Keep reducing n for every # number with two set bits. while (n > 0) : # Consider all lower set bits # for current higher set bit y = 0 while (y < x) : # Print current number print((1 << x) + (1 << y), end = " " ) # If we have found n numbers n -= 1 if (n == 0) : return # Consider next lower bit # for current higher bit. y += 1 # Increment higher set bit x += 1 # Driver code printTwoSetBitNums(4) # This code is contributed # by Smitha
C#
// C# program to print first n numbers
// with exactly two set bits
using System;
class GFG
{
// Function to print first n
// numbers with two set bits
static void printTwoSetBitNums(int n)
{
// Initialize higher of
// two sets bits
int x = 1;
// Keep reducing n for every
// number with two set bits
while (n > 0)
{
// Consider all lower set bits
// for current higher set bit
int y = 0;
while (y < x)
{
// Print current number
Console.Write(((1 << x) +
(1 << y)) +" ");
// If we have found n numbers
n--;
if (n == 0)
return;
// Consider next lower bit
// for current higher bit.
y++;
}
// Increment higher set bit
x++;
}
}
// Driver program
public static void Main()
{
int n = 4;
printTwoSetBitNums(n);
}
}
// This code is contributed by Anant Agarwal.
PHP
<?php
// PHP program to print
// first n numbers with
// exactly two set bits
// Prints first n numbers
// with two set bits
function printTwoSetBitNums($n)
{
// Initialize higher of
// two sets bits
$x = 1;
// Keep reducing n for
// every number with
// two set bits.
while ($n > 0)
{
// Consider all lower set
// bits for current higher
// set bit
$y = 0;
while ($y < $x)
{
// Print current number
echo (1 << $x) + (1 << $y), " ";
// If we have found n numbers
$n--;
if ($n == 0)
return;
// Consider next lower
// bit for current
// higher bit.
$y++;
}
// Increment higher set bit
$x++;
}
}
// Driver code
printTwoSetBitNums(4);
// This code is contributed by Ajit
?>
Javascript
<script>
// Javascript program to print first n numbers
// with exactly two set bits
// Prints first n numbers with two set bits
function printTwoSetBitNums(n)
{
// Initialize higher of two sets bits
let x = 1;
// Keep reducing n for every number
// with two set bits.
while (n > 0)
{
// Consider all lower set bits for
// current higher set bit
let y = 0;
while (y < x)
{
// Print current number
document.write((1 << x) + (1 << y) + " ");
// If we have found n numbers
n--;
if (n == 0)
return;
// Consider next lower bit for current
// higher bit.
y++;
}
// Increment higher set bit
x++;
}
}
// Driver code
printTwoSetBitNums(4);
// This code is contributed by Mayank Tyagi
</script>
Producción :
3 5 6 9
Complejidad de tiempo : O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Bharath Reddy Appareddy . 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