2835. Minimum Operations to Form Subsequence With Target Sum
Problem Description
You are provided with an array nums
where each element is a non-negative power of 2
. A target
integer is also given. Your task is to make a subsequence of nums
that adds up to target
. A subsequence can be formed by removing some elements from the array without changing the order of the remaining elements.
Operations that you are allowed to perform involve choosing an element nums[i]
greater than 1
, removing it from the array, and adding two occurrences of nums[i] / 2
to the end of the array. The goal is to find the minimum number of such operations required to reach the target
sum using a subsequence of the modified array. If it's not possible to reach the target
, you should return -1
.
To clarify:
- The sequence is 0-indexed.
- Operations can only be performed on elements greater than
1
. - You are adding two halves of the number you remove back to the array.
- We are interested in returning the smallest possible number of operations.
- We are only creating subsequences, not permutations. Order matters.
Intuition
The solution approach requires decomposing the target
into powers of 2
, similar to binary representation. Since every element in nums
is a power of 2
, the sum that we need to hit (the target
) can be seen as a sum of certain powers of 2
. What we want is to find which powers of 2
are needed and in what quantity to reach the target
.
The intuition behind the solution comes from the binary representation of the target. Since every number in nums
is a power of 2
, the target's binary representation indicates which powers of 2
are required. What we do is build up smaller powers of 2
to form the larger ones needed. This is akin to converting coins you possess into coins of lower denominations to make exact change.
Hereās a breakdown of the intuition:
- Check if the sum of all elements in
nums
is less than the target. If yes, we can't possibly hit the target, so return-1
. - Count how many times each power of
2
appears innums
. This is prepared for knowing whether we have enough "coins" of each power to reach each bit in target's binary representation. - Iterate over each bit of
target
from LSB to MSB. - For each bit set in
target
, we need to make sure we have a power of2
available to match this bit.- If not enough of that power is available, we build it up from smaller powers by doing our defined operation, which "breaks" a number in half and adds two of the halves.
- Each build-up is counted as a conversion operation.
- Add the number of operations at each step, and continue until the entire binary representation of
target
is processed. - If we process the whole representation successfully, the total count of operations is the answer we return.
Learn more about Greedy patterns.
Solution Approach
The algorithm takes advantage of bit manipulation and greedy approach to minimize the number of operations required to achieve a subsequence that sums to target
. It initializes a frequency array cnt
to represent the count of each power of 2
present in nums
. Since any num
in the array is a non-negative power of 2
, up to 2^31
could be included; hence the size of cnt
is 32
, for the 32
bits.
Here's a detailed walk-through of the implementation:
-
Sum Check: Before we even start, we ensure that the sum of all elements in
nums
is at leasttarget
. If not, we immediately return-1
. -
Count Powers of
2
: Next, we count occurrences of each power of2
, which is done through bitwise operations. For eachx
innums
, we use a bitwise shift and bitwise AND to find which power of2
it represents and increment the corresponding count incnt
. -
Iterate Over Target Bits:
- We then iterate through the bits of
target
, starting with the least significant bit (LSB). - If the current bit in the
target
is not set (0
), there is nothing to match, so we move on to the next more significant bit. - When we encounter a bit set to
1
, it indicates we need a power of2
of that magnitude to contribute to the sum.
- We then iterate through the bits of
-
Build Required Powers:
- If the necessary power of
2
is not available, we need to build it up from the available smaller powers by performing operations which effectively "combine" two elements of a smaller power of2
into one of the next higher power. - We ensure that if we are looking for
2^i
, all lower powers are combined as much as possible (cnt[j]
is halved andcnt[j + 1]
incremented accordingly).
- If the necessary power of
-
Optimize and Perform Operations:
- If there's no count available (
cnt[j]
is0
) for the required power2^j
, we convert all available powers. This is where the greedy strategy comes in. We keep running our conversion operation until we've built the required power of2
. - Each action of converting smaller powers to bigger ones is a single operation. The difference
j - i
contributes to the total operations performed, as it reflects converting2^i
to2^j
. - When building up a required power, we subtract one from the higher power and reset
j
toi
since we just used up one power of2^j
to match a set bit in thetarget
.
- If there's no count available (
-
Result: The iteration continues until all bits in
target
are processed (did we match all bits?). If we achieved our goal, the total number of operations (ans
) is returned. If it was impossible to meet a bit requirement, the first part of the code would have already returned-1
.
The pattern used in this solution is a mix of bit manipulation (to read individual bits in the target
and convert nums
into count of powers of 2
) and a greedy approach that always opts to convert the available smallest powers of 2
to the necessary ones in the minimum number of operations.
Using the Python bitwise shift >>
and bitwise AND &
, each number's contribution to the target sum is analyzed bit by bit, and the array cnt
is updated to reflect how many operations are needed to "break down" larger powers of 2
into smaller ones to match the target's bit pattern.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have the following nums
array and target
:
nums = [4, 8, 1, 2]
target = 11
(binary representation:1011
)
Initial Preparation
- Calculate the sum of the
nums
:4 + 8 + 1 + 2 = 15
. Since 15 is greater than 11, we can proceed. - Construct the frequency array
cnt
:[1, 1, 1, 0, 1]
. We have one1 (2^0)
, one2 (2^1)
, one4 (2^2)
, zero8 (2^3)
, and one16 (2^4)
.
Iterate Over Target Bits (from LSB to MSB)
- Bit 0 (
2^0
): Target is1
. We have one1
incnt
, so we use it. No operation needed. - Bit 1 (
2^1
): Target is1
. We have one2
incnt
, so we use it. No operation needed. - Bit 2 (
2^2
): Target is0
. Move to the next bit. - Bit 3 (
2^3
): Target is1
, butcnt
for2^3
is0
. We need to build this power up.- Since we need
2^3
and we have one2^2
, we do not have enough of2^2
to double and make one2^3
. However, we have2^4
available which can be broken down.
- Since we need
Building Required Powers
- We 'break' our
2^4
into two2^3
s. One operation is performed. Nowcnt
is:[1, 1, 1, 2, 0]
. - We use one
2^3
for our target. Nowcnt
is:[1, 1, 1, 1, 0]
.
Final Steps
- We have used all bits set in
target
, and the number of operations performed is 1. - We return the total number of operations:
1
.
The process shows how we break down powers of 2
only when necessary to reach our target
and keep the operations to a minimum. In this case, converting a 2^4
to two 2^3
s ensured that we could create the target
sum of 11
from the subsequence of the modified array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def min_operations(self, nums: List[int], target: int) -> int:
5 # Calculate the initial sum of the elements in the array.
6 total_sum = sum(nums)
7 # If the sum is less than the target, it's impossible to reach the target.
8 if total_sum < target:
9 return -1
10
11 # Count the occurrences of set bits at each position for all numbers.
12 count_set_bits = [0] * 32
13 for num in nums:
14 for i in range(32):
15 if num & (1 << i):
16 count_set_bits[i] += 1
17
18 current_index = 0
19 bit_index = 0
20 operations = 0
21 while True:
22 # Find the next set bit in the target from the current_index.
23 while current_index < 32 and (target >> current_index & 1) == 0:
24 current_index += 1
25 # If all bits in the target are processed, exit the loop.
26 if current_index == 32:
27 break
28
29 # Consolidate the current bits into the next position for unset bits in the target.
30 while bit_index < current_index:
31 count_set_bits[bit_index + 1] += count_set_bits[bit_index] // 2
32 count_set_bits[bit_index] %= 2
33 bit_index += 1
34
35 # Ensure that there is at least one set bit for the current position.
36 while bit_index < 32 and count_set_bits[bit_index] == 0:
37 bit_index += 1
38 # If we've reached beyond the 31st bit (last position), return -1
39 if bit_index == 32:
40 return -1
41 count_set_bits[bit_index] = 1
42
43 # Calculate the operations needed for the current bit and add it to the total operations.
44 operations += bit_index - current_index
45 # Decrement the count of set bits at the current position as we've used one to reach the target bit.
46 count_set_bits[bit_index] -= 1
47
48 # Set current_index to the new bit_index for the upcoming bit consolidation
49 bit_index = current_index
50 # Move forward to the next bit in the target.
51 current_index += 1
52
53 # Return the total operations required to reach the target.
54 return operations
55
1class Solution {
2
3 // This method finds the minimum number of operations to reach a target value
4 // by incrementing or decrementing elements in the nums list.
5 public int minOperations(List<Integer> nums, int target) {
6 long sum = 0; // To hold the total sum of the list
7 int[] bitCounts = new int[32]; // Array to count the occurrences of bits at each position
8
9 // Counting bits for each number in the array and summing up the numbers
10 for (int num : nums) {
11 sum += num;
12 for (int i = 0; i < 32; ++i) {
13 if ((num >> i & 1) == 1) {
14 ++bitCounts[i];
15 }
16 }
17 }
18
19 // If the total sum is less than the target, it's not possible to reach target
20 if (sum < target) {
21 return -1;
22 }
23
24 // Initialize pointers and the answer count
25 int i = 0, j = 0; // i is for target bit index, j for bitCounts index
26 int operations = 0; // To hold the minimum number of operations
27
28 while (true) {
29 // Move i to the next bit that is a 1 in the target
30 while (i < 32 && (target >> i & 1) == 0) {
31 ++i;
32 }
33 // If all bits of the target are processed, return the result
34 if (i == 32) {
35 return operations;
36 }
37 // Propagate carries in bitCounts up to the current bit of interest
38 while (j < i) {
39 bitCounts[j + 1] += bitCounts[j] / 2; // Carry over to the next bit position
40 bitCounts[j] %= 2; // Remainder stays at current position
41 ++j;
42 }
43 // Find the next bit that can be used to fulfill the target bit requirement
44 while (j < 32 && bitCounts[j] == 0) {
45 ++j;
46 }
47
48 // If j has reached the limit, no bit available to fulfill the target requirement
49 if (j == 32) {
50 break;
51 }
52
53 // Increment operation count based on the number of moves needed
54 operations += j - i;
55 // Use the bit from position j to fulfill the requirement at position i
56 --bitCounts[j];
57 // Reset the counter as we have already fulfilled the bit at position i
58 j = i;
59 // Move to the next bit of the target
60 ++i;
61 }
62
63 // If we exit the loop, it means we couldn't fulfill the bit requirements; return -1
64 return -1;
65 }
66}
67
1class Solution {
2public:
3 int minOperations(vector<int>& nums, int target) {
4 // Initialize sum and count array for tracking number of set bits per bit position
5 long long sum = 0;
6 int count_bits[32] = {};
7
8 // Preprocess the input array to compute total sum and number of set bits for each bit position
9 for (int num : nums) {
10 sum += num;
11 for (int i = 0; i < 32; ++i) {
12 if (num & (1 << i)) {
13 ++count_bits[i];
14 }
15 }
16 }
17
18 // If the total sum is less than the target, it's impossible to reach the target
19 if (sum < target) {
20 return -1;
21 }
22
23 // Initialize two pointers for bit positions and an answer variable to count operations
24 int i = 0, j = 0, operations_count = 0;
25
26 // The main loop for reaching the target
27 while (true) {
28 // Move i to the next set bit in the target
29 while (i < 32 && ((target >> i) & 1) == 0) {
30 ++i;
31 }
32 // If we've processed all bits, return the operations count
33 if (i == 32) {
34 return operations_count;
35 }
36 // Carry operation: shift half of the set bits from lower to higher bits
37 while (j < i) {
38 count_bits[j + 1] += count_bits[j] / 2;
39 count_bits[j] %= 2;
40 ++j;
41 }
42 // Find the position for flipping the bit to match the target
43 while (count_bits[j] == 0) {
44 // This is the step where we need to flip a lower bit to higher
45 count_bits[j] = 1;
46 ++j;
47 }
48 // Increase the operation count by the difference in positions
49 operations_count += j - i;
50 // Decrease the count since we've used one bit from the j-th position
51 --count_bits[j];
52 // Reset j back to i for the next iteration
53 j = i;
54 // Move to the next bit in the target
55 ++i;
56 }
57 }
58};
59
1function minOperations(nums: number[], target: number): number {
2 // Initialize sum of all numbers
3 let sum = 0;
4 // Initialize a counter array to hold the count of bits at each position
5 const bitCount: number[] = Array(32).fill(0);
6 // Calculate the sum and populate the bit count array
7 for (const num of nums) {
8 sum += num;
9 for (let i = 0; i < 32; ++i) {
10 if ((num >> i) & 1) {
11 ++bitCount[i];
12 }
13 }
14 }
15 // If the sum is less than the target, it's not possible to achieve the target
16 if (sum < target) {
17 return -1;
18 }
19
20 // Initialize variables for the answer and bit indexes
21 let answer = 0, bitIndex = 0, carryIndex = 0;
22
23 // Main loop to perform operation until target is reached
24 while (true) {
25 // Find the first bit position in the target that is 1
26 while (bitIndex < 32 && ((target >> bitIndex) & 1) === 0) {
27 ++bitIndex;
28 }
29 // If all bits are checked, return the answer
30 if (bitIndex === 32) {
31 return answer;
32 }
33 // Handle carry-over for creating a binary number with required operations
34 while (carryIndex < bitIndex) {
35 bitCount[carryIndex + 1] += bitCount[carryIndex] >> 1;
36 bitCount[carryIndex] %= 2;
37 ++carryIndex;
38 }
39 // Ensure the current bit position has at least one 1 bit; otherwise, increment the answer
40 while (bitCount[carryIndex] === 0) {
41 bitCount[carryIndex] = 1;
42 carryIndex++;
43 }
44 // Increment the number of operations based on the distance between bitIndex and carryIndex
45 answer += carryIndex - bitIndex;
46 // Decrement the 1 bit that was used for the current bitIndex
47 bitCount[carryIndex]--;
48 // Reset carryIndex to bitIndex for the next iteration
49 carryIndex = bitIndex;
50 // Move to the next bit position in the target number
51 bitIndex++;
52 }
53}
54
Time and Space Complexity
The given code intends to count the minimum number of operations required to reduce a list of numbers such that their sum equals a given target. An operation consists of dividing a non-zero element of the array by 2 and taking the floor.
Time Complexity
The time complexity of the code is determined by several nested loops and operations on the cnt
list which has fixed size of 32 (since we're considering the binary representation of integers within 32 bits).
-
The first
for
loop iterates over all the elements in the givennums
list. Its complexity isO(n)
, wheren
is the number of elements innums
. -
Inside this loop, there is a nested
for
loop iterating at most 32 times (for each bit in the integer's binary representation). This makes the complexity of code inside the first loopO(32n) = O(n)
, because the 32 is a constant factor. -
After initializing
i
andj
, we have a while loop that continues untili
equals 32. In the worst case, this loop could run up to 32 times. -
Within the said while loop, we have several other while loops that increase
i
andj
. Sincei
andj
index through the bit positions at most 32 times, these while loops contribute at mostO(32)
, which can be considered a fixed size and thus a constant factor. -
Each operation within the loops has a constant time complexity.
Combining these, the overall time complexity of this code snippet is O(n)
, where n
is the length of nums
because we can treat all the other operations as constants.
Space Complexity
The space complexity is determined by the additional space used by the algorithm excluding the input size.
-
We have a constant-sized list
cnt
of size 32 to keep track of the count of bits set at different positions. -
Variables
i
,j
, andans
also take up space, but they are constant-sized and do not depend on the input size.
Given this, the space complexity of the algorithm is O(1)
, as the space used does not scale with the input size; it remains constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!