prefix [ i ] is going to store the number of elements which are a power of two till i ( including i ) .
prefix = [ 0 ] * ( MAX + 1 ) NEW_LINE def isPowerOfTwo ( x ) : NEW_LINE INDENT if ( x and ( not ( x & ( x - 1 ) ) ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT