Minimum Operations to Form Subsequence With Target Sum
You are given a 0-indexed array nums consisting of non-negative powers of 2, and an integer target.
In one operation, you must apply the following changes to the array:
- Choose any element of the array
nums[i]such thatnums[i] > 1. - Remove
nums[i]from the array. - Add two occurrences of
nums[i] / 2to the end ofnums.
Return the minimum number of operations you need to perform so that nums contains a subsequence whose elements sum to target. If it is impossible to obtain such a subsequence, return -1.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1
Input
nums = [1,2,8], target = 7Output
1Splitting 8 once gives [1, 2, 4, 4], which contains the subsequence [1, 2, 4] summing to 7, and no shorter sequence works.
Example 2
Input
nums = [1,32,1,2], target = 12Output
2Splitting 32 into two 16s and then one 16 into two 8s gives a subsequence [1, 1, 2, 8] that sums to 12, and no shorter sequence works.
Constraints
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 2^30
- nums consists only of non-negative powers of two.
- 1 <= target < 2^31
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.