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 nvoid findSetBits(int n){ for (int i = 0; i <= n; i++) cout << __builtin_popcount(i) << " ";}// Driver codeint main(){ int n = 5; findSetBits(n); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to find the count// of set bits in all the// integers from 0 to nstatic void findSetBits(int n){ for (int i = 0; i <= n; i++) System.out.print(Integer.bitCount(i) + " ");}// Driver codepublic static void main(String[] args) { int n = 5; findSetBits(n);}}// This code is contributed by Rajput-Ji |
Python 3
# Python 3 implementation of the approachdef 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 ndef findSetBits(n): for i in range(n + 1): print(count(i), end = " ") # Driver codeif __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> |
Output:
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 nvoid 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 codeint main(){ int n = 5; findSetBits(n); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to find the count// of set bits in all the// integers from 0 to nstatic 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 codepublic 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 approachusing System; class GFG{// Function to find the count// of set bits in all the// integers from 0 to nstatic 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 codepublic 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> |
Output:
0 1 1 2 1 2
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
