#2835
Minimum Operations to Form Subsequence With Target Sum
international master · 1935 · lc hard +32 · verified · 32.4% accepted · 554 likes · top 10%
Description
A 0-indexed array nums of non-negative powers of 2 and an integer target are given.
In one operation, choose nums[i] > 1, remove it, and append two copies of nums[i] / 2.
Return the minimum number of operations needed so that some subsequence of nums sums to target, or -1 if impossible.
A subsequence is derived from an array by deleting some or no elements without reordering the rest.
Example 1:
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:
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:
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.
Code
1
2
3