Dado un número entero no negativo N , la tarea es encontrar el recuento de bits establecidos para cada número de 0 a N .
Ejemplos:
Entrada: N = 3
Salida: 0 1 1 2
0, 1, 2 y 3 se pueden escribir en binario como 0, 1, 10 y 11.
El número de 1 en su representación binaria es 0, 1, 1 y 2.
Entrada : N = 5
Salida: 0 1 1 2 1 2
Enfoque ingenuo: Ejecute un ciclo de 0 a N y use la función de conteo de bits incorporada __builtin_popcount() , encuentre la cantidad de bits establecidos en todos los enteros requeridos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count
// of set bits in all the
// integers from 0 to n
void findSetBits(int n)
{
for (int i = 0; i <= n; i++)
cout << __builtin_popcount(i) << " ";
}
// Driver code
int main()
{
int n = 5;
findSetBits(n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to find the count
// of set bits in all the
// integers from 0 to n
static void findSetBits(int n)
{
for (int i = 0; i <= n; i++)
System.out.print(Integer.bitCount(i) + " ");
}
// Driver code
public static void main(String[] args)
{
int n = 5;
findSetBits(n);
}
}
// This code is contributed by Rajput-Ji
Python 3
# Python 3 implementation of the approach def count(n): count = 0 while (n): count += n & 1 n >>= 1 return count # Function to find the count # of set bits in all the # integers from 0 to n def findSetBits(n): for i in range(n + 1): print(count(i), end = " ") # Driver code if __name__ == '__main__': n = 5 findSetBits(n) # This code is contributed by Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int count(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to find the count
// of set bits in all the
// integers from 0 to n
static void findSetBits(int n)
{
for (int i = 0; i <= n; i++)
Console.Write(count(i)+" ");
}
// Driver code
public static void Main(String []args)
{
int n = 5;
findSetBits(n);
}
}
// This code is contributed by SHUBHAMSINGH10
Javascript
<script>
// Javascript implementation of the approach
function count(n)
{
let count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to find the count
// of set bits in all the
// integers from 0 to n
function findSetBits(n)
{
for (let i = 0; i <= n; i++)
document.write(count(i)+" ");
}
let n = 5;
findSetBits(n);
</script>
0 1 1 2 1 2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Enfoque eficiente: escribamos la representación binaria de números en el rango (0, 6).
0 en binario – 000
1 en binario – 001
2 en binario – 010
3 en binario – 011
4 en binario – 100
5 en binario – 101
6 en binario – 110
Ya que, cualquier número par se puede escribir como (2 * i) y cualquier número impar se puede escribir como (2 * i + 1) donde i es un número natural.
2, 4 y 3, 6 tienen el mismo número de 1 en su representación binaria, ya que multiplicar cualquier número equivale a desplazarlo a la izquierda por 1 (lea aquí) .
De manera similar, cualquier número par 2 * i e i tendrá el mismo número de 1 en su representación binaria.
El número de 1 en 5 (101) es igual al número de 1 en la representación binaria de 2 + 1. Entonces, en el caso de cualquier número impar (2 * i + 1) , será (número de 1 en la representación binaria de i ) + 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count
// of set bits in all the
// integers from 0 to n
void findSetBits(int n)
{
// dp[i] will store the count
// of set bits in i
int dp[n + 1];
// Initialise the dp array
memset(dp, 0, sizeof(dp));
// Count of set bits in 0 is 0
cout << dp[0] << " ";
// For every number starting from 1
for (int i = 1; i <= n; i++) {
// If current number is even
if (i % 2 == 0) {
// Count of set bits in i is equal to
// the count of set bits in (i / 2)
dp[i] = dp[i / 2];
}
// If current element is odd
else {
// Count of set bits in i is equal to
// the count of set bits in (i / 2) + 1
dp[i] = dp[i / 2] + 1;
}
// Print the count of set bits in i
cout << dp[i] << " ";
}
}
// Driver code
int main()
{
int n = 5;
findSetBits(n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to find the count
// of set bits in all the
// integers from 0 to n
static void findSetBits(int n)
{
// dp[i] will store the count
// of set bits in i
int []dp = new int[n + 1];
// Count of set bits in 0 is 0
System.out.print(dp[0] + " ");
// For every number starting from 1
for (int i = 1; i <= n; i++)
{
// If current number is even
if (i % 2 == 0)
{
// Count of set bits in i is equal to
// the count of set bits in (i / 2)
dp[i] = dp[i / 2];
}
// If current element is odd
else
{
// Count of set bits in i is equal to
// the count of set bits in (i / 2) + 1
dp[i] = dp[i / 2] + 1;
}
// Print the count of set bits in i
System.out.print(dp[i] + " ");
}
}
// Driver code
public static void main(String []args)
{
int n = 5;
findSetBits(n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to find the count of set bits # in all the integers from 0 to n def findSetBits(n) : # dp[i] will store the count # of set bits in i # Initialise the dp array dp = [0] * (n + 1); # Count of set bits in 0 is 0 print(dp[0], end = " "); # For every number starting from 1 for i in range(1, n + 1) : # If current number is even if (i % 2 == 0) : # Count of set bits in i is equal to # the count of set bits in (i / 2) dp[i] = dp[i // 2]; # If current element is odd else : # Count of set bits in i is equal to # the count of set bits in (i / 2) + 1 dp[i] = dp[i // 2] + 1; # Print the count of set bits in i print(dp[i], end = " "); # Driver code if __name__ == "__main__" : n = 5; findSetBits(n); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find the count
// of set bits in all the
// integers from 0 to n
static void findSetBits(int n)
{
// dp[i] will store the count
// of set bits in i
int []dp = new int[n + 1];
// Count of set bits in 0 is 0
Console.Write(dp[0] + " ");
// For every number starting from 1
for (int i = 1; i <= n; i++)
{
// If current number is even
if (i % 2 == 0)
{
// Count of set bits in i is equal to
// the count of set bits in (i / 2)
dp[i] = dp[i / 2];
}
// If current element is odd
else
{
// Count of set bits in i is equal to
// the count of set bits in (i / 2) + 1
dp[i] = dp[i / 2] + 1;
}
// Print the count of set bits in i
Console.Write(dp[i] + " ");
}
}
// Driver code
public static void Main(String []args)
{
int n = 5;
findSetBits(n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to find the count
// of set bits in all the
// integers from 0 to n
function findSetBits(n)
{
// dp[i] will store the count
// of set bits in i
let dp = new Array(n + 1);
dp.fill(0);
// Count of set bits in 0 is 0
document.write(dp[0] + " ");
// For every number starting from 1
for (let i = 1; i <= n; i++)
{
// If current number is even
if (i % 2 == 0)
{
// Count of set bits in i is equal to
// the count of set bits in (i / 2)
dp[i] = dp[parseInt(i / 2, 10)];
}
// If current element is odd
else
{
// Count of set bits in i is equal to
// the count of set bits in (i / 2) + 1
dp[i] = dp[parseInt(i / 2, 10)] + 1;
}
// Print the count of set bits in i
document.write(dp[i] + " ");
}
}
let n = 5;
findSetBits(n);
// This code is contributed by divyeshrabadiya07
</script>
0 1 1 2 1 2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por ShrabanaBiswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA