Given an integer x and an array arr[] each element of which is a power of 2. The task is to find the minimum number of integer powers of 2 from the array which when added give x. If it is not possible to represent x with the given array elements then print -1.
Examples:
Input: arr[] = {2, 4, 8, 2, 4}, x = 14
Output: 3
14 can be written as 8 + 4 + 2
Input: arr[] = {2, 4, 8, 2, 4}, x = 5
Output: -1
5 cannot be represented as the sum any elements from the given array.
Approach: For each power of 2 let’s calculate the number of elements in the given array with the value equals this. Let’s call it cnt. It is obvious that we can obtain the value x greedily (because all fewer values of elements are divisors of all greater values of elements).
Now let’s iterate over all powers of 2 from 30 to 0. Let’s deg be the current degree. We can take min(x / 2deg, cntdeg) elements with the value equals 2deg. Let it be cur. Add cur to the answer and subtract 2deg * cur from x. Repeat the process until the x can no longer be reduced. If after iterating over all powers, x is still non-zero then print -1. Otherwise, print the answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum number// of given integer powers of 2 required// to represent a number as sum of these powersint power_of_two(int n, int a[], int x){ // To store the count of powers of two vector<int> cnt(31); for (int i = 0; i < n; ++i) { // __builtin_ctz(a[i]) returns the count // of trailing 0s in a[i] ++cnt[__builtin_ctz(a[i])]; } int ans = 0; for (int i = 30; i >= 0 && x > 0; --i) { // If current power is available // in the array and can be used int need = min(x >> i, cnt[i]); // Update the answer ans += need; // Reduce the number x -= (1 << i) * need; } // If the original number is not reduced to 0 // It cannot be represented as the sum // of the given powers of 2 if (x > 0) ans = -1; return ans;}// Driver codeint main(){ int arr[] = { 2, 2, 4, 4, 8 }, x = 6; int n = sizeof(arr) / sizeof(arr[0]); cout << power_of_two(n, arr, x); return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG{ // __builtin_ctz(a[i]) returns the count // of trailing 0s in a[i] static int __builtin_ctz(int a){ int count = 0; for(int i = 0; i < 40; i++) if(((a >> i) & 1) == 0) { count++; } else break; return count;}// Function to return the minimum number // of given integer powers of 2 required // to represent a number as sum of these powers static int power_of_two(int n, int a[], int x) { // To store the count of powers of two Vector<Integer> cnt = new Vector<Integer>(); for (int i = 0; i < 31; ++i) cnt.add(0); for (int i = 0; i < n; ++i) { // __builtin_ctz(a[i]) returns the count // of trailing 0s in a[i] cnt.set(__builtin_ctz(a[i]), (cnt.get(__builtin_ctz(a[i]))==null) ? 1 : cnt.get(__builtin_ctz(a[i]))+1); } int ans = 0; for (int i = 30; i >= 0 && x > 0; --i) { // If current power is available // in the array and can be used int need = Math.min(x >> i, cnt.get(i)); // Update the answer ans += need; // Reduce the number x -= (1 << i) * need; } // If the original number is not reduced to 0 // It cannot be represented as the sum // of the given powers of 2 if (x > 0) ans = -1; return ans; } // Driver code public static void main(String args[]){ int arr[] = { 2, 2, 4, 4, 8 }, x = 6; int n = arr.length; System.out.println(power_of_two(n, arr, x)); } }// This code is contributed by Arnab Kundu |
python
# Python3 implementation of the approach# Function to return the minimum number# of given eger powers of 2 required# to represent a number as sum of these powersdef power_of_two( n, a, x): # To store the count of powers of two cnt=[0 for i in range(31)] for i in range(n): # __builtin_ctz(a[i]) returns the count # of trailing 0s in a[i] count = 0 xx = a[i] while ((xx & 1) == 0): xx = xx >> 1 count += 1 cnt[count]+=1 ans = 0 for i in range(30,-1,-1): if x<=0: continue # If current power is available # in the array and can be used need = min(x >> i, cnt[i]) # Update the answer ans += need # Reduce the number x -= (1 << i) * need # If the original number is not reduced to 0 # It cannot be represented as the sum # of the given powers of 2 if (x > 0): ans = -1 return ans# Driver codearr=[2, 2, 4, 4, 8 ]x = 6n = len(arr)print(power_of_two(n, arr, x))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System;class GFG{ // __builtin_ctz(a[i]) returns the count // of trailing 0s in a[i] static int __builtin_ctz(int a){ int count = 0; for(int i = 0; i < 40; i++) if(((a >> i) & 1) == 0) { count++; } else break; return count;}// Function to return the minimum number // of given integer powers of 2 required // to represent a number as sum of these powers static int power_of_two(int n, int []a, int x) { // To store the count of powers of two int[] cnt = new int[32]; for (int i = 0; i < n; ++i) { // __builtin_ctz(a[i]) returns the count // of trailing 0s in a[i] cnt[__builtin_ctz(a[i])] = cnt[__builtin_ctz(a[i])] == 0?1 : cnt[__builtin_ctz(a[i])] + 1; } int ans = 0; for (int i = 30; i >= 0 && x > 0; --i) { // If current power is available // in the array and can be used int need = Math.Min(x >> i, cnt[i]); // Update the answer ans += need; // Reduce the number x -= (1 << i) * need; } // If the original number is not reduced to 0 // It cannot be represented as the sum // of the given powers of 2 if (x > 0) ans = -1; return ans; } // Driver code static void Main(){ int []arr = { 2, 2, 4, 4, 8 }; int x = 6; int n = arr.Length; Console.WriteLine(power_of_two(n, arr, x)); } }// This code is contributed by mits |
Javascript
<script>// JavaScript implementation of the approach// Function to return the minimum number// of given integer powers of 2 required// to represent a number as sum of these powersfunction power_of_two( n, a, x){ // To store the count of powers of two let cnt = []; for(let i = 0;i<31;i++) cnt.push(0); for (let i = 0; i < n; ++i) { // __builtin_ctz(a[i]) returns the count // of trailing 0s in a[i] let count = 0; let xx = a[i]; while ((xx & 1) == 0){ xx = xx >> 1 count += 1 } cnt[count]+=1; } let ans = 0; for (let i = 30; i >= 0 && x > 0; --i) { // If current power is available // in the array and can be used let need = Math.min(x >> i, cnt[i]); // Update the answer ans += need; // Reduce the number x -= (1 << i) * need; } // If the original number is not reduced to 0 // It cannot be represented as the sum // of the given powers of 2 if (x > 0) ans = -1; return ans;}// Driver codelet arr = [ 2, 2, 4, 4, 8 ], x = 6;let n = arr.length;document.write( power_of_two(n, arr, x));</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(32), since no extra space has been taken.
Another Approach(Space optimization):
We can Binary search to find the index such that a[index] <= x .and reduce x to x-a[index] and increase ans by 1. and until our x become 0. If there is not any index of array a[] at any time such that a[index] <= x .we simply assign ans=-1 and print ans.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;//Function to find index such that a[index] <= xint binarysearch(int arr[], int N, int x){ int l = 0, r = N- 1, index = -1; while (l <= r) { int mid = (l + r) / 2; // Checking if the middle element is less // than or equal equal to x if (arr[mid] <= x) { index = mid ; l = mid + 1; } else { r = mid - 1; } } // return -1 if there is no index such that a[index] <= x //return that index such that a[index] <= x return index;}// Function to return the minimum number// of given integer powers of 2 required// to represent a number as sum of these powersint power_of_two(int n, int a[], int x){ int ans=0; while(x!=0) { // Binary search to find index of array a // such that a[index] <= x int index = binarysearch(a , n, x); if(index == -1) { // if there is no element in the array // such that a[index] <= x ans=-1; break; } else{ //if there is a index of array a such that // a[index] <= x ,then increase ans by 1 x =x- a[index]; ans++; } } //return ans return ans;}// Driver codeint main(){ int arr[] = { 2, 2, 4, 4, 8 }, x = 6; int n = sizeof(arr) / sizeof(arr[0]); //Function call cout << power_of_two(n, arr, x); return 0;}// This code is contributed by nikhilsainiofficial546 |
Java
public class Main { // Function to find index such that a[index] <= x static int binarysearch(int[] arr, int N, int x) { int l = 0, r = N - 1, index = -1; while (l <= r) { int mid = (l + r) / 2; // Checking if the middle element is less // than or equal equal to x if (arr[mid] <= x) { index = mid; l = mid + 1; } else { r = mid - 1; } } // return -1 if there is no index such that a[index] <= x // return that index such that a[index] <= x return index; } // Function to return the minimum number // of given integer powers of 2 required // to represent a number as sum of these powers static int power_of_two(int n, int[] a, int x) { int ans = 0; while (x != 0) { // Binary search to find index of array a // such that a[index] <= x int index = binarysearch(a, n, x); if (index == -1) { // if there is no element in the array // such that a[index] <= x ans = -1; break; } else { // if there is a index of array a such that // a[index] <= x ,then increase ans by 1 x -= a[index]; ans += 1; } } // return ans return ans; } // Driver code public static void main(String[] args) { int[] arr = {2, 2, 4, 4, 8}; int x = 6; int n = arr.length; // Function call System.out.println(power_of_two(n, arr, x)); }} |
Python3
# Function to find index such that a[index] <= xdef binarysearch(arr, N, x): l, r, index = 0, N-1, -1 while l <= r: mid = (l + r) // 2 # Checking if the middle element is less # than or equal equal to x if arr[mid] <= x: index = mid l = mid + 1 else: r = mid - 1 # return -1 if there is no index such that a[index] <= x #return that index such that a[index] <= x return index# Function to return the minimum number# of given integer powers of 2 required# to represent a number as sum of these powersdef power_of_two(n, a, x): ans = 0 while x != 0: # Binary search to find index of array a # such that a[index] <= x index = binarysearch(a, n, x) if index == -1: # if there is no element in the array # such that a[index] <= x ans = -1 break else: # if there is a index of array a such that # a[index] <= x ,then increase ans by 1 x -= a[index] ans += 1 #return ans return ans# Driver codeif __name__ == '__main__': arr = [2, 2, 4, 4, 8] x = 6 n = len(arr) #Function call print(power_of_two(n, arr, x)) |
C#
using System;class Gfg{ // Function to find index such that a[index] <= x static int binarysearch(int[] arr, int N, int x) { int l = 0, r = N - 1, index = -1; while (l <= r) { int mid = (l + r) / 2; // Checking if the middle element is less // than or equal equal to x if (arr[mid] <= x) { index = mid; l = mid + 1; } else { r = mid - 1; } } // return -1 if there is no index such that a[index] <= x // return that index such that a[index] <= x return index; } // Function to return the minimum number // of given integer powers of 2 required // to represent a number as sum of these powers static int power_of_two(int n, int[] a, int x) { int ans = 0; while (x != 0) { // Binary search to find index of array a // such that a[index] <= x int index = binarysearch(a, n, x); if (index == -1) { // if there is no element in the array // such that a[index] <= x ans = -1; break; } else { // if there is a index of array a such that // a[index] <= x, then increase ans by 1 x -= a[index]; ans++; } } // return ans return ans; } static void Main(string[] args) { int[] arr = { 2, 2, 4, 4, 8 }; int x = 6; int n = arr.Length; // Function call Console.WriteLine(power_of_two(n, arr, x)); }} |
Javascript
//javascript equivalent of the above code// Function to find index such that a[index] <= xfunction binarysearch(arr, N, x) { let l = 0; let r = N-1; let index = -1; while (l <= r) { let mid = Math.trunc((l + r) / 2); // Checking if the middle element is less // than or equal equal to x if (arr[mid] <= x) { index = mid; l = mid + 1; } else { r = mid - 1; } } // return -1 if there is no index such that a[index] <= x //return that index such that a[index] <= x return index;}// Function to return the minimum number// of given integer powers of 2 required// to represent a number as sum of these powersfunction power_of_two(n, a, x) { let ans = 0; while (x != 0) { // Binary search to find index of array a // such that a[index] <= x let index = binarysearch(a, n, x); if (index == -1) { // if there is no element in the array // such that a[index] <= x ans = -1; break; } else { // if there is a index of array a such that // a[index] <= x ,then increase ans by 1 x -= a[index]; ans += 1; } } //return ans return ans;}// Driver codelet arr = [2, 2, 4, 4, 8];let x = 6;let n = arr.length; //Function callconsole.log(power_of_two(n, arr, x)); |
Output
2
Time Complexity: O(x*logn) because binary search has a time complexity of O(logn)
Auxiliary Space: O(1)
Another Approach(Dynamic Programming.): We can define dp[i] as the minimum number of powers of 2 required to represent the number i.
Algorithm:
- Create an array dp of size x+1 to store the minimum number of powers of 2 required to represent each number from 0 to x.
- Initialize dp[0] to 0 since we don’t need any powers of 2 and to represent 0 and use a nested loop to iterate over each number i from 1 to x, and for each i, iterate over each power of 2 in the array arr and that is less than or equal to i.
- Calculate the minimum number of powers of 2 required to represent the difference i – arr[j], and add 1 to this to get the minimum number of powers of 2 required to represent i.
- Store this value in dp[i] and finally, return dp[x] if it is less than or equal to x and indicating that it is possible to represent x using the given array elements, otherwise return -1.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int min_powers_of_2(int arr[], int n, int x) { int dp[x+1]; dp[0] = 0; for (int i = 1; i <= x; i++) { dp[i] = INT_MAX; for (int j = 0; j < n; j++) { if (arr[j] <= i) { int sub_res = dp[i - arr[j]]; if (sub_res != INT_MAX) { dp[i] = min(dp[i], sub_res + 1); } } } } return dp[x] == INT_MAX ? -1 : dp[x];}int main() { int arr[] = {2, 2, 4, 4, 8}; int n = sizeof(arr) / sizeof(arr[0]); int x = 6; int result = min_powers_of_2(arr, n, x); cout << result << endl; return 0;} |
Java
public class Main { public static int minPowersOf2(int[] arr, int n, int x) { // Create an array to store minimum powers of 2 // required to make each sum int[] dp = new int[x + 1]; // Initialize the first element of the array as 0 // since we need 0 powers of 2 to make a sum of 0 dp[0] = 0; // Iterate through all possible sums from 1 to x for (int i = 1; i <= x; i++) { // Initialize the current sum's minimum powers // of 2 requirement as maximum possible value dp[i] = Integer.MAX_VALUE; // Iterate through the array of available // numbers for (int j = 0; j < n; j++) { // Check if the current number can be used // to make the current sum if (arr[j] <= i) { // Calculate the minimum powers of 2 // required to make the remaining sum int subRes = dp[i - arr[j]]; // Check if a valid sub-result exists // (i.e., the remaining sum is // achievable) if (subRes != Integer.MAX_VALUE) { // Update the current sum's minimum // powers of 2 requirement if the // new option is better dp[i] = Math.min(dp[i], subRes + 1); } } } } // Check if it's not possible to make the sum x with // the available numbers if (dp[x] == Integer.MAX_VALUE) { return -1; } else { // Return the minimum powers of 2 required to // make the sum x return dp[x]; } } public static void main(String[] args) { int[] arr = { 2, 2, 4, 4, 8 }; int n = arr.length; int x = 6; // Calculate the minimum powers of 2 required to // make sum x int result = minPowersOf2(arr, n, x); // Print the result to the console System.out.println(result); }} |
Python3
import sysdef min_powers_of_2(arr, n, x): dp = [sys.maxsize] * (x + 1) dp[0] = 0 for i in range(1, x + 1): for j in range(n): if arr[j] <= i: sub_res = dp[i - arr[j]] if sub_res != sys.maxsize: dp[i] = min(dp[i], sub_res + 1) return -1 if dp[x] == sys.maxsize else dp[x]if __name__ == '__main__': arr = [2, 2, 4, 4, 8] n = len(arr) x = 6 result = min_powers_of_2(arr, n, x) print(result) |
C#
using System;namespace MinPowersOf2Example{ class Program { static int MinPowersOf2(int[] arr, int n, int x) { int[] dp = new int[x + 1]; dp[0] = 0; for (int i = 1; i <= x; i++) { dp[i] = int.MaxValue; for (int j = 0; j < n; j++) { if (arr[j] <= i) { int sub_res = dp[i - arr[j]]; if (sub_res != int.MaxValue) { dp[i] = Math.Min(dp[i], sub_res + 1); } } } } return dp[x] == int.MaxValue ? -1 : dp[x]; } static void Main(string[] args) { int[] arr = { 2, 2, 4, 4, 8 }; int n = arr.Length; int x = 6; int result = MinPowersOf2(arr, n, x); Console.WriteLine(result); } }} |
Javascript
// Function to find the minimum number of powers of 2 needed to sum up to 'x'function minPowersOf2(arr, n, x) { // Creating an array 'dp' to store minimum // counts for each value from 0 to 'x' const dp = Array(x + 1).fill(Number.MAX_SAFE_INTEGER); // Base case: Minimum count to make 0 is 0 dp[0] = 0; // Iterate over each value from 1 to 'x' for (let i = 1; i <= x; i++) { // Iterate over the elements in the array 'arr' for (let j = 0; j < n; j++) { // If the current element is less than or equal to 'i' if (arr[j] <= i) { // Calculate the sub-result based on the previous count (dp[i - arr[j]]) const subResult = dp[i - arr[j]]; // If sub-result is not the maximum value (indicating it's possible to reach i - arr[j]) if (subResult !== Number.MAX_SAFE_INTEGER) { // Update dp[i] with the minimum count dp[i] = Math.min(dp[i], subResult + 1); } } } } // If dp[x] is still set to its initial maximum value, it means 'x' cannot be achieved // Otherwise, dp[x] contains the minimum count to achieve 'x' return dp[x] === Number.MAX_SAFE_INTEGER ? -1 : dp[x];}// Main functionfunction main() { const arr = [2, 2, 4, 4, 8]; const n = arr.length; const x = 6; const result = minPowersOf2(arr, n, x); console.log(result);}// Calling the main functionmain();// This code is contributed by Dwaipayan Bandyopadhyay |
Output
2
Time Complexity: O(nx), where n is the size of the array and x is the given number to be represented. This is because we are iterating over each number from 1 to x, and for each number, we are iterating over each element in the array arr that is less than or equal to that number.
Auxiliary Space: O(x), because we are creating an array dp of size x+1 to store the minimum number of powers of 2 required to represent each number from 0 to x.
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!
