Minimum size of set having either element in range [ 0 , X ] or an odd power of 2 with sum N | Python program for the above approach ; Function to find the highest odd power of 2 in the range [ 0 , N ] ; If P is even , subtract 1 ; Function to find the minimum operations to make N ; If N is odd and X = 0 , then no valid set exist ; Stores the minimum possible size of the valid set ; Loop to subtract highest odd power of 2 while X < N , step 2 ; If N > 0 , then increment the value of answer by 1 ; Return the resultant size of set ; Driver Code
import math NEW_LINE def highestPowerof2 ( n ) : NEW_LINE INDENT p = int ( math . log ( n , 2 ) ) NEW_LINE if p % 2 == 0 : NEW_LINE INDENT p -= 1 NEW_LINE DEDENT return int ( pow ( 2 , p ) ) NEW_LINE DEDENT def minStep ( N , X ) : NEW_LINE INDENT if N % 2 and X == 0 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT size = 0 NEW_LINE while X < N : NEW_LINE INDENT N -= highestPowerof2 ( N ) NEW_LINE size += 1 NEW_LINE DEDENT if N : NEW_LINE INDENT size += 1 NEW_LINE DEDENT return size NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 11 NEW_LINE X = 2 NEW_LINE print ( minStep ( N , X ) ) NEW_LINE DEDENT