2835. Minimum Operations to Form Subsequence With Target Sum

HardGreedyBit ManipulationArray
Leetcode Link

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 in nums. 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 of 2 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

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:

  1. Sum Check: Before we even start, we ensure that the sum of all elements in nums is at least target. If not, we immediately return -1.

  2. Count Powers of 2: Next, we count occurrences of each power of 2, which is done through bitwise operations. For each x in nums, we use a bitwise shift and bitwise AND to find which power of 2 it represents and increment the corresponding count in cnt.

  3. 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 of 2 of that magnitude to contribute to the sum.

  4. 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 of 2 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 and cnt[j + 1] incremented accordingly).

  5. Optimize and Perform Operations:

    • If there's no count available (cnt[j] is 0) for the required power 2^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 of 2.
    • 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 converting 2^i to 2^j.
    • When building up a required power, we subtract one from the higher power and reset j to i since we just used up one power of 2^j to match a set bit in the target.

  6. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the maximum element can be found in:

Example 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 one 1 (2^0), one 2 (2^1), one 4 (2^2), zero 8 (2^3), and one 16 (2^4).

Iterate Over Target Bits (from LSB to MSB)

  • Bit 0 (2^0): Target is 1. We have one 1 in cnt, so we use it. No operation needed.
  • Bit 1 (2^1): Target is 1. We have one 2 in cnt, so we use it. No operation needed.
  • Bit 2 (2^2): Target is 0. Move to the next bit.
  • Bit 3 (2^3): Target is 1, but cnt for 2^3 is 0. We need to build this power up.
    • Since we need 2^3 and we have one 2^2, we do not have enough of 2^2 to double and make one 2^3. However, we have 2^4 available which can be broken down.

Building Required Powers

  • We 'break' our 2^4 into two 2^3s. One operation is performed. Now cnt is: [1, 1, 1, 2, 0].
  • We use one 2^3 for our target. Now cnt 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^3s 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
Not Sure What to Study? Take the 2-min Quiz：

Which technique can we use to find the middle of a linked list?

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 given nums list. Its complexity is O(n), where n is the number of elements in nums.

  • 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 loop O(32n) = O(n), because the 32 is a constant factor.

  • After initializing i and j, we have a while loop that continues until i 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 and j. Since i and j index through the bit positions at most 32 times, these while loops contribute at most O(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, and ans 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.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫