Calculate the number of set bits for every number from 0 to N | C ++ implementation of the approach ; Function to find the count of set bits in all the integers from 0 to n ; dp [ i ] will store the count of set bits in i ; Count of set bits in 0 is 0 ; For every number starting from 1 ; If current number is even ; Count of set bits in i is equal to the count of set bits in ( i / 2 ) ; If current element is odd ; Count of set bits in i is equal to the count of set bits in ( i / 2 ) + 1 ; Print the count of set bits in i ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findSetBits ( int n ) { int dp [ n + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; cout << dp [ 0 ] << " ▁ " ; for ( int i = 1 ; i <= n ; i ++ ) { if ( i % 2 == 0 ) { dp [ i ] = dp [ i / 2 ] ; } else { dp [ i ] = dp [ i / 2 ] + 1 ; } cout << dp [ i ] << " ▁ " ; } } int main ( ) { int n = 5 ; findSetBits ( n ) ; return 0 ; }