prefix [ i ] is going to store the number of elements which are a power of two till i ( including i ) .
int prefix [ MAX + 1 ] ; bool isPowerOfTwo ( int x ) { if ( x && ( ! ( x & ( x - 1 ) ) ) ) return true ; return false ; }