4041. Minimum Operations to Form Subset Sum II

SourceWeekly Contest 517 Q4DifficultyHardRating2099

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