4040. Minimum Operations to Form Subset Sum I

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, all multiplication operations performed on it must occur before any division operations performed on it.

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 = [5,6,10], sum = 4

Output: 3

Explanation:

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

Example 2:

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 3:

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

Output: -1

Explanation:

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

Constraints:

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

Solutions

Solution 1: 0-1 Knapsack

Thinking

Multiplying and dividing the same element \(a\) and \(b\) times can be replaced by \(|a-b|\) one-way operations; mixing the two only wastes steps. Each element is therefore scaled only by multiplying by \(2\), only by dividing by \(2\), or not taken.

The resulting (value, cost) pairs are \(0\)-\(1\) knapsack items with capacity \(\textit{sum}\). For \(n\le 100\) and \(S\le 5000\), enumerating \(O(\log S)\) scalings is acceptable.

Updating capacities backward ensures each element is used at most once. If \(f[\textit{sum}]\) stays infinite, there is no solution.

Applying \(a\) multiplications followed by \(b\) divisions to an element gives \(\lfloor x \times 2^a / 2^b \rfloor\), which is exactly \(x \times 2^{a-b}\) or \(\lfloor x / 2^{b-a} \rfloor\). The same value is reachable with only \(|a - b|\) operations instead of \(a + b\), so mixing the two directions is never worthwhile. Therefore each element has only two families of reachable values: \(x \times 2^i\) or \(\lfloor x / 2^i \rfloor\), each costing \(i\) operations, while an element left out of the subset costs nothing.

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 every value \(y\) that \(x\) can become together with its cost \(i\), and update \(f[w]\) with \(f[w - y] + i\) 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 S)\), and the space complexity is \(O(S)\). Here, \(n\) is the length 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:
        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 <<= 1
                i, y = 1, x >> 1
                while y > 0:
                    if y <= w:
                        f[w] = min(f[w], f[w - y] + i)
                    i += 1
                    y >>= 1
        return -1 if f[sum] == inf else f[sum]

class Solution {
    public int minOperations(int[] nums, int sum) {
        int inf = Integer.MAX_VALUE / 2;
        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 <<= 1;
                }

                i = 1;
                y = x >> 1;
                while (y > 0) {
                    if (y <= w) {
                        f[w] = Math.min(f[w], f[w - y] + i);
                    }
                    ++i;
                    y >>= 1;
                }
            }
        }

        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) {
                int i = 0, y = x;
                while (y <= w) {
                    f[w] = min(f[w], f[w - y] + i);
                    ++i;
                    y <<= 1;
                }

                i = 1;
                y = x >> 1;
                while (y > 0) {
                    if (y <= w) {
                        f[w] = min(f[w], f[w - y] + i);
                    }
                    ++i;
                    y >>= 1;
                }
            }
        }

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

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-- {
            i, y := 0, x
            for y <= w {
                f[w] = min(f[w], f[w-y]+i)
                i++
                y <<= 1
            }

            i, y = 1, x>>1
            for y > 0 {
                if y <= w {
                    f[w] = min(f[w], f[w-y]+i)
                }
                i++
                y >>= 1
            }
        }
    }

    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) {
            let i = 0;
            let y = x;

            while (y <= w) {
                f[w] = Math.min(f[w], f[w - y] + i);
                ++i;
                y *= 2;
            }

            i = 1;
            y = Math.floor(x / 2);

            while (y > 0) {
                if (y <= w) {
                    f[w] = Math.min(f[w], f[w - y] + i);
                }
                ++i;
                y = Math.floor(y / 2);
            }
        }
    }

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

4040. Minimum Operations to Form Subset Sum I

Description

Solutions

Solution 1: 0-1 Knapsack

Comments