Minimum size of set having either element in range [ 0 , X ] or an odd power of 2 with sum N | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int highestPowerof2 ( int n ) { int p = int ( log2 ( n ) ) ; if ( p % 2 == 0 ) p -= 1 ; return int ( pow ( 2 , p ) ) ; } int minStep ( int N , int X ) { if ( N % 2 and X == 0 ) return -1 ; int size = 0 ; while ( X < N ) { N -= highestPowerof2 ( N ) ; size += 1 ; } if ( N ) size += 1 ; return size ; } int main ( ) { int N = 11 ; int X = 2 ; cout << ( minStep ( N , X ) ) ; }