Super Hard💀Dynamic Programming DSA Question asked by Leetcode in Weekly Contest 517(Q3,4040)
Minimum Operations to Form Subset Sum I - Video Solution
Watch 10 video solutions for Minimum Operations to Form Subset Sum I, a medium level problem. This walkthrough by Kumar K [Amazon] has 3,897 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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] = 5twice:5 → 2 → 1, costing 2 operations. - Divide
nums[1] = 6once: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] = 10once:10 → 5, costing 1 operation. - Multiply
nums[1] = 2twice: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
numssum to 8, so the answer is -1.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 5001 <= sum <= 5000