Given two positive integers N and X, the task is to find the size of the smallest set of integers such that the sum of all elements of the set is N and each set element is either in the range [0, X] or is an odd power of 2. If it is not possible to find such a size of the set then print “-1”.
Examples:
Input: N = 11, X = 2
Output: 3
Explanation: The set {1, 2, 8} is the set of minimum number of elements such that the sum of elements is 11 and each element is either in range [0, 2] (i.e, 1 and 2) or is an odd power of 2 (i.e., 8 = 23).Input: N = 3, X = 0
Output: -1
Explanation : No valid set exist.
Approach: The given problem can be solved using the below steps:
- Maintain a variable size that stores the minimum possible size of a valid set and initialize it with 0.
- Iterate until the value of N is greater than X and perform the following steps:
- Subtract the largest odd power i of 2 that is less than or equal to N from N.
- Increment the value of size by 1.
- If the value of N is positive, then increment the value of size by 1.
- After completing the above steps, print the value of size as the required result.
Below is the implementation of the above approach:
C++
// CPP program for the above approach#include<bits/stdc++.h>using namespace std;// Function to find the highest odd power// of 2 in the range [0, N]int highestPowerof2(int n){ int p = int(log2(n)); // If P is even, subtract 1 if(p % 2 == 0) p -= 1; return int(pow(2, p));}// Function to find the minimum operations// to make Nint minStep(int N, int X){ // If N is odd and X = 0, then no // valid set exist if(N % 2 and X == 0) return -1; // Stores the minimum possible size // of the valid set int size = 0; // Loop to subtract highest odd power // of 2 while X < N, step 2 while(X < N){ N -= highestPowerof2(N); size += 1; } // If N > 0, then increment the value // of answer by 1 if(N) size += 1; // Return the resultant size of set return size;}// Driver Codeint main(){ int N = 11; int X = 2; cout<<(minStep(N, X));}// This code is contributed by ipg2016107. |
Java
// Java program for the above approachimport java.io.*;class GFG {// Function to find the highest odd power// of 2 in the range [0, N]static int highestPowerof2(int n){ int p = (int)Math.floor(Math.log(n)/Math.log(2.0)); // If P is even, subtract 1 if(p % 2 == 0) p -= 1; int result = (int)(Math.pow(2,p)); return result;}// Function to find the minimum operations// to make Nstatic int minStep(int N, int X){ // If N is odd and X = 0, then no // valid set exist if (N % 2 != 0 && X == 0) return -1; // Stores the minimum possible size // of the valid set int size = 0; // Loop to subtract highest odd power // of 2 while X < N, step 2 while(X < N){ N -= highestPowerof2(N); size += 1; } // If N > 0, then increment the value // of answer by 1 if (N != 0) size += 1; // Return the resultant size of set return size;}// Driver Codepublic static void main (String[] args) { int N = 11; int X = 2; System.out.println(minStep(N, X));}}// This code is contributed by shivanisinghss2110 |
Python3
# Python program for the above approachimport math# Function to find the highest odd power# of 2 in the range [0, N]def highestPowerof2(n): p = int(math.log(n, 2)) # If P is even, subtract 1 if p % 2 == 0: p -= 1 return int(pow(2, p)) # Function to find the minimum operations# to make Ndef minStep(N, X): # If N is odd and X = 0, then no # valid set exist if N % 2 and X == 0: return -1 # Stores the minimum possible size # of the valid set size = 0 # Loop to subtract highest odd power # of 2 while X < N, step 2 while X < N: N -= highestPowerof2(N) size += 1 # If N > 0, then increment the value # of answer by 1 if N: size += 1 # Return the resultant size of set return size # Driver Codeif __name__ == '__main__': N = 11 X = 2 print(minStep(N, X)) |
C#
// C# program for the above approachusing System;class GFG {// Function to find the highest odd power// of 2 in the range [0, N]static int highestPowerof2(int n){ int p = (int)Math.Floor(Math.Log(n)/Math.Log(2.0)); // If P is even, subtract 1 if(p % 2 == 0) p -= 1; int result = (int)(Math.Pow(2,p)); return result;}// Function to find the minimum operations// to make Nstatic int minStep(int N, int X){ // If N is odd and X = 0, then no // valid set exist if (N % 2 != 0 && X == 0) return -1; // Stores the minimum possible size // of the valid set int size = 0; // Loop to subtract highest odd power // of 2 while X < N, step 2 while(X < N){ N -= highestPowerof2(N); size += 1; } // If N > 0, then increment the value // of answer by 1 if (N != 0) size += 1; // Return the resultant size of set return size;}// Driver Codepublic static void Main (String[] args){ int N = 11; int X = 2; Console.Write(minStep(N, X));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to find the highest odd power// of 2 in the range [0, N]function highestPowerof2(n) { let p = Math.floor(Math.log2(n)); // If P is even, subtract 1 if (p % 2 == 0) { p -= 1 } return Math.pow(2, p)}// Function to find the minimum operations// to make Nfunction minStep(N, X) { // If N is odd and X = 0, then no // valid set exist if (N % 2 != 0 && X == 0) return -1 // Stores the minimum possible size // of the valid set let size = 0 // Loop to subtract highest odd power // of 2 while X < N, step 2 while (X < N) { N -= highestPowerof2(N) size += 1 } // If N > 0, then increment the value // of answer by 1 if (N != 0) size += 1 // Return the resultant size of set return size;}// Driver Codelet N = 11let X = 2document.write(minStep(N, X))// This code is contributed by Potta Lokesh</script> |
Output:
3
Time Complexity: O(log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
