Calculate the number of set bits for every number from 0 to N | Java 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
class GFG { static void findSetBits ( int n ) { int [ ] dp = new int [ n + 1 ] ; System . out . print ( 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 ; } System . out . print ( dp [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int n = 5 ; findSetBits ( n ) ; } }