Calculate the number of set bits for every number from 0 to N
Given a non-negative integer N, the task is to find the count of set bits for every number from 0 to N.
Examples:
Input: N = 3
Output: 0 1 1 2
0, 1, 2 and 3 can be written in binary as 0, 1, 10 and 11.
The number of 1âs in their binary representation are 0, 1, 1 and 2.
Input: N = 5
Output: 0 1 1 2 1 2
Naive approach: Run a loop from 0 to N and using inbuilt bit count function __builtin_popcount(), find the number of set bits in all the required integers.
Below is the implementation of the above approach:
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
Time Complexity: O(n)
Auxiliary Space: O(1)
Efficient approach: Let us write the binary representation of numbers in the range (0, 6).
0 in binary â 000
1 in binary â 001
2 in binary â 010
3 in binary â 011
4 in binary â 100
5 in binary â 101
6 in binary â 110
Since, any even number can be written as (2 * i) and any odd number can be written as (2 * i + 1) where i is a natural number.
2, 4 and 3, 6 have equal number of 1âs in their binary representation as multiplying any number is equivalent to shifting it left by 1 (read here).
Similarly, any even number 2 * i and i will have equal number of 1âs in its binary representation.
Number of 1âs in 5(101) is equal to number of 1âs in 2âs binary representation + 1. So in case of any odd number (2 * i + 1), it will be (number of 1âs in the binary representation of i) + 1.
Below is the implementation of the above approach:
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
Time Complexity: O(n)
Auxiliary Space: O(n)