4041. Minimum Operations to Form Subset Sum II

Description

You are given an integer array nums and an integer sum.

In one operation, choose an element with current value x and replace it with either 2 * x or floor(x / 2).

For each element, multiplication and division operations may be performed in any order.

Return the minimum number of operations needed so that some subset of the resulting array has a sum exactly equal to sum. If it is impossible, return -1.

The floor() function returns the integer part of the division.

Example 1:

Input: nums = [10,2], sum = 13

Output: 3

Explanation:

Divide nums[0] = 10 once: 10 → 5, costing 1 operation.
Multiply nums[1] = 2 twice: 2 → 4 → 8, costing 2 operations.
After these operations, nums = [5, 8]. The subset {5, 8} sums to 13 using 3 operations in total.

Example 2:

Input: nums = [6,3], sum = 8

Output: 2

Explanation:

Turn nums[1] = 3 into 2 using 2 operations:
- Divide nums[1] to get 1.
- Multiply nums[1] = 1 to get 2.
After these operations, nums = [6, 2]. The subset {6, 2} sums to 8 using 2 operations in total.

Example 3:

Input: nums = [2,2], sum = 7

Output: -1

Explanation:

No sequence of operations lets a subset of nums sum to 7, so the answer is -1.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 500
1 <= sum <= 5000

Solutions

Solution 1: 0-1 Knapsack

Thinking

Unlike the previous problem, multiplies and divides may be interleaved. A multiply that happens before a divide cancels, so every sequence reduces to \(i\) divides followed by \(j\) multiplies: the value is \(\lfloor x/2^i\rfloor\times 2^j\) at cost \(i+j\).

We still fill capacity \(\textit{sum}\) with a \(0\)-\(1\) knapsack, now enumerating an extra dimension per element. Backward updates keep at most one pair \((i,j)\) per element.

If \(f[\textit{sum}]\) stays infinite the answer is \(-1\).

Unlike the previous problem, multiplications and divisions may be interleaved in any order. Notice that a multiplication immediately followed by a division is a no-op, since \(\lfloor 2x / 2 \rfloor = x\), so any multiplication that happens before a division can be cancelled against it, wasting two operations. After repeatedly cancelling such pairs, every sequence reduces to "divide \(i\) times, then multiply \(j\) times", which turns \(x\) into \(\lfloor x / 2^i \rfloor \times 2^j\) at a cost of \(i + j\) operations.

This turns the problem into a 0-1 knapsack: every element contributes at most one (value, cost) pair, and we want the minimum cost to fill a capacity of exactly \(\textit{sum}\).

We define \(f[w]\) as the minimum number of operations needed for a subset to sum to exactly \(w\), with \(f[0] = 0\) and all other entries set to \(+\infty\). For each element \(x\), we iterate the capacity \(w\) from large to small, enumerate the number of divisions \(i\) and multiplications \(j\) to get the value \(y = \lfloor x / 2^i \rfloor \times 2^j\), and update \(f[w]\) with \(f[w - y] + i + j\) whenever \(y \leq w\). If \(f[\textit{sum}]\) is still \(+\infty\) at the end, no valid sequence of operations exists and we return \(-1\); otherwise we return \(f[\textit{sum}]\).

The time complexity is \(O(n \times S \times \log M \times \log S)\), and the space complexity is \(O(S)\). Here, \(n\) and \(M\) are the length and the maximum value of the array \(\textit{nums}\), and \(S\) is the given \(\textit{sum}\).

Python3JavaC++GoTypeScript

class Solution:
    def minOperations(self, nums: List[int], sum: int) -> int:
        inf = 10**9
        f = [0] + [inf] * sum

        for x in nums:
            for w in range(sum, -1, -1):
                i, y = 0, x
                while y <= w:
                    f[w] = min(f[w], f[w - y] + i)
                    i += 1
                    y *= 2

                i, y = 1, x // 2
                while y > 0:
                    j, z = 0, y
                    while z <= w:
                        f[w] = min(f[w], f[w - z] + i + j)
                        j += 1
                        z *= 2
                    i += 1
                    y //= 2

        return -1 if f[sum] == inf else f[sum]

class Solution {
    public int minOperations(int[] nums, int sum) {
        int inf = (int) 1e9;
        int[] f = new int[sum + 1];
        Arrays.fill(f, inf);
        f[0] = 0;

        for (int x : nums) {
            for (int w = sum; w >= 0; --w) {
                int i = 0, y = x;
                while (y <= w) {
                    f[w] = Math.min(f[w], f[w - y] + i);
                    ++i;
                    y *= 2;
                }

                i = 1;
                y = x / 2;
                while (y > 0) {
                    int j = 0, z = y;
                    while (z <= w) {
                        f[w] = Math.min(f[w], f[w - z] + i + j);
                        ++j;
                        z *= 2;
                    }
                    ++i;
                    y /= 2;
                }
            }
        }

        return f[sum] == inf ? -1 : f[sum];
    }
}

class Solution {
public:
    int minOperations(vector<int>& nums, int sum) {
        const int inf = 1e9;
        vector<int> f(sum + 1, inf);
        f[0] = 0;

        for (int x : nums) {
            for (int w = sum; w >= 0; --w) {
                for (int i = 0, y = x; y <= w; i++, y *= 2) {
                    f[w] = min(f[w], f[w - y] + i);
                }

                for (int i = 1, y = x / 2; y > 0; i++, y /= 2) {
                    for (int j = 0, z = y; z <= w; j++, z *= 2) {
                        f[w] = min(f[w], f[w - z] + i + j);
                    }
                }
            }
        }

        return f[sum] < inf ? f[sum] : -1;
    }
};

func minOperations(nums []int, sum int) int {
    const inf = int(1e9)

    f := make([]int, sum+1)
    for i := range f {
        f[i] = inf
    }
    f[0] = 0

    for _, x := range nums {
        for w := sum; w >= 0; w-- {
            for i, y := 0, x; y <= w; i, y = i+1, y*2 {
                f[w] = min(f[w], f[w-y]+i)
            }

            for i, y := 1, x/2; y > 0; i, y = i+1, y/2 {
                for j, z := 0, y; z <= w; j, z = j+1, z*2 {
                    f[w] = min(f[w], f[w-z]+i+j)
                }
            }
        }
    }

    if f[sum] == inf {
        return -1
    }
    return f[sum]
}

function minOperations(nums: number[], sum: number): number {
    const inf = 1e9;
    const f = Array(sum + 1).fill(inf);
    f[0] = 0;

    for (const x of nums) {
        for (let w = sum; w >= 0; --w) {
            for (let i = 0, y = x; y <= w; ++i, y *= 2) {
                f[w] = Math.min(f[w], f[w - y] + i);
            }

            for (let i = 1, y = Math.floor(x / 2); y > 0; ++i, y = Math.floor(y / 2)) {
                for (let j = 0, z = y; z <= w; ++j, z *= 2) {
                    f[w] = Math.min(f[w], f[w - z] + i + j);
                }
            }
        }
    }

    return f[sum] === inf ? -1 : f[sum];
}

4041. Minimum Operations to Form Subset Sum II

Description

Solutions

Solution 1: 0-1 Knapsack

Comments