Calculate the number of set bits for every number from 0 to N | 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 Initialise the dp array ; 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
def findSetBits ( n ) : NEW_LINE INDENT dp = [ 0 ] * ( n + 1 ) ; NEW_LINE print ( dp [ 0 ] , end = " ▁ " ) ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( i % 2 == 0 ) : NEW_LINE INDENT dp [ i ] = dp [ i // 2 ] ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = dp [ i // 2 ] + 1 ; NEW_LINE DEDENT print ( dp [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 ; NEW_LINE findSetBits ( n ) ; NEW_LINE DEDENT