Problem

You are given a 0-indexed array nums consisting of non-negative powers of 2, and an integer target.

In one operation, you must apply the following changes to the array:

  • Choose any element of the array nums[i] such that nums[i] > 1.
  • Remove nums[i] from the array.
  • Add two occurrences of nums[i] / 2 to the end of nums.

Return the _minimum number of operations you need to perform so that _nums contains asubsequence whose elements sum to target. If it is impossible to obtain such a subsequence, return -1.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Examples

Example 1

1
2
3
4
5

Input: nums = [1,2,8], target = 7
Output: 1
Explanation: In the first operation, we choose element nums[2]. The array becomes equal to nums = [1,2,4,4].
At this stage, nums contains the subsequence [1,2,4] which sums up to 7.
It can be shown that there is no shorter sequence of operations that results in a subsequnce that sums up to 7.

Example 2

1
2
3
4
5
6

Input: nums = [1,32,1,2], target = 12
Output: 2
Explanation: In the first operation, we choose element nums[1]. The array becomes equal to nums = [1,1,2,16,16].
In the second operation, we choose element nums[3]. The array becomes equal to nums = [1,1,2,16,8,8]
At this stage, nums contains the subsequence [1,1,2,8] which sums up to 12.
It can be shown that there is no shorter sequence of operations that results in a subsequence that sums up to 12.

Example 3

1
2
3

Input: nums = [1,32,1], target = 35
Output: -1
Explanation: It can be shown that no sequence of operations results in a subsequence that sums up to 35.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 230
  • nums consists only of non-negative powers of two.
  • 1 <= target < 231

Solution

Method 1 – Greedy & Bit Counting

Intuition

We want to form target using powers of two. If we lack a needed power, we can split a larger power into two smaller ones. The minimum number of splits is the number of times we need to break down larger powers to get enough of each bit in target.

Approach

  1. Count the number of each power of two in nums.
  2. For each bit in target (from lowest to highest), check if we have enough of that power in nums.
  3. If not, split larger powers (by breaking them down) until we have enough.
  4. Count the number of splits (operations) needed.
  5. If not possible, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minOperations(vector<int>& nums, int target) {
        vector<int> cnt(31, 0);
        for (int v : nums) cnt[__builtin_ctz(v)]++;
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            if ((target >> i) & 1) {
                if (cnt[i]) cnt[i]--;
                else {
                    int j = i + 1;
                    while (j < 31 && !cnt[j]) ++j;
                    if (j == 31) return -1;
                    while (j > i) {
                        cnt[j]--;
                        cnt[j-1] += 2;
                        ans++;
                        j--;
                    }
                    cnt[i]--;
                }
            }
            if (i < 30) cnt[i+1] += cnt[i]/2;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func minOperations(nums []int, target int) int {
    cnt := make([]int, 31)
    for _, v := range nums {
        for i := 0; i < 31; i++ {
            if v == 1<<i {
                cnt[i]++
                break
            }
        }
    }
    ans := 0
    for i := 0; i < 31; i++ {
        if (target>>i)&1 == 1 {
            if cnt[i] > 0 {
                cnt[i]--
            } else {
                j := i + 1
                for j < 31 && cnt[j] == 0 {
                    j++
                }
                if j == 31 {
                    return -1
                }
                for j > i {
                    cnt[j]--
                    cnt[j-1] += 2
                    ans++
                    j--
                }
                cnt[i]--
            }
        }
        if i < 30 {
            cnt[i+1] += cnt[i] / 2
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int minOperations(int[] nums, int target) {
        int[] cnt = new int[31];
        for (int v : nums) cnt[Integer.numberOfTrailingZeros(v)]++;
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            if (((target >> i) & 1) == 1) {
                if (cnt[i] > 0) cnt[i]--;
                else {
                    int j = i + 1;
                    while (j < 31 && cnt[j] == 0) ++j;
                    if (j == 31) return -1;
                    while (j > i) {
                        cnt[j]--;
                        cnt[j-1] += 2;
                        ans++;
                        j--;
                    }
                    cnt[i]--;
                }
            }
            if (i < 30) cnt[i+1] += cnt[i]/2;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun minOperations(nums: IntArray, target: Int): Int {
        val cnt = IntArray(31)
        for (v in nums) cnt[v.countTrailingZeroBits()]++
        var ans = 0
        for (i in 0 until 31) {
            if ((target shr i) and 1 == 1) {
                if (cnt[i] > 0) cnt[i]--
                else {
                    var j = i + 1
                    while (j < 31 && cnt[j] == 0) j++
                    if (j == 31) return -1
                    while (j > i) {
                        cnt[j]--
                        cnt[j-1] += 2
                        ans++
                        j--
                    }
                    cnt[i]--
                }
            }
            if (i < 30) cnt[i+1] += cnt[i]/2
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def minOperations(self, nums: list[int], target: int) -> int:
        cnt = [0] * 31
        for v in nums:
            cnt[v.bit_length() - 1] += 1
        ans: int = 0
        for i in range(31):
            if (target >> i) & 1:
                if cnt[i]:
                    cnt[i] -= 1
                else:
                    j = i + 1
                    while j < 31 and not cnt[j]:
                        j += 1
                    if j == 31:
                        return -1
                    while j > i:
                        cnt[j] -= 1
                        cnt[j-1] += 2
                        ans += 1
                        j -= 1
                    cnt[i] -= 1
            if i < 30:
                cnt[i+1] += cnt[i] // 2
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

impl Solution {
    pub fn min_operations(nums: Vec<i32>, target: i32) -> i32 {
        let mut cnt = vec![0; 31];
        for v in nums {
            cnt[v.trailing_zeros() as usize] += 1;
        }
        let mut ans = 0;
        for i in 0..31 {
            if (target >> i) & 1 == 1 {
                if cnt[i] > 0 {
                    cnt[i] -= 1;
                } else {
                    let mut j = i + 1;
                    while j < 31 && cnt[j] == 0 {
                        j += 1;
                    }
                    if j == 31 {
                        return -1;
                    }
                    while j > i {
                        cnt[j] -= 1;
                        cnt[j-1] += 2;
                        ans += 1;
                        j -= 1;
                    }
                    cnt[i] -= 1;
                }
            }
            if i < 30 {
                cnt[i+1] += cnt[i] / 2;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    minOperations(nums: number[], target: number): number {
        const cnt = Array(31).fill(0);
        for (const v of nums) cnt[Math.floor(Math.log2(v))]++;
        let ans = 0;
        for (let i = 0; i < 31; ++i) {
            if ((target >> i) & 1) {
                if (cnt[i]) cnt[i]--;
                else {
                    let j = i + 1;
                    while (j < 31 && !cnt[j]) ++j;
                    if (j == 31) return -1;
                    while (j > i) {
                        cnt[j]--;
                        cnt[j-1] += 2;
                        ans++;
                        j--;
                    }
                    cnt[i]--;
                }
            }
            if (i < 30) cnt[i+1] += Math.floor(cnt[i]/2);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(31 * n) — For each bit, we may scan up to n elements, but n is at most 1000.
  • 🧺 Space complexity: O(1) — Only a fixed-size array is used.