Horje
Minimum size of set having either element in range [0, X] or an odd power of 2 with sum N

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 N
int 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 Code
int main(){
    int N = 11;
    int X = 2;
    cout<<(minStep(N, X));
 
}
 
// This code is contributed by ipg2016107.

Java

// Java program for the above approach
import 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 N
static 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 Code
public 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 approach
import 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 N
def 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 Code
if __name__ == '__main__':
    N = 11
    X = 2
    print(minStep(N, X))

C#

// C# program for the above approach
using 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 N
static 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 Code
public 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 N
function 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 Code
let N = 11
let X = 2
 
document.write(minStep(N, X))
 
// This code is contributed by Potta Lokesh
</script>

Output: 

3

 

Time Complexity: O(log N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Find range of values for S in given Array with values satisfying [ arr[i] = floor((i*S)/K) ] Find range of values for S in given Array with values satisfying [ arr[i] = floor((i*S)/K) ]
Find Binary permutations of given size not present in the Array Find Binary permutations of given size not present in the Array
Find longest subarray with Prime sum in given Array Find longest subarray with Prime sum in given Array
Check if possible to make Array sum equal to Array product by replacing exactly one element Check if possible to make Array sum equal to Array product by replacing exactly one element
Count of even sum triplets in the array for Q range queries Count of even sum triplets in the array for Q range queries

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 9



 

Horje