You are given a positive integer k. Initially, you have an array nums = [1].
You can perform any of the following operations on the array any number of times (possibly zero):
1.Return the minimum number of operations required to make the sum of elements of the final array greater than or equal to k.
Example 1:
Input: k = 11
Output: 5
Explanation:
We can do the following operations on the array nums = [1]:
1 three times. The resulting array is nums = [4].nums = [4,4,4].The sum of the final array is 4 + 4 + 4 = 12 which is greater than or equal to k = 11.
The total number of operations performed is 3 + 2 = 5.
Example 2:
Input: k = 1
Output: 0
Explanation:
The sum of the original array is already greater than or equal to 1, so no operations are needed.
Constraints:
1 <= k <= 105Problem Overview: You start with an array containing a single element [1]. Two operations are allowed: increment any element by 1, or append a copy of an existing element. The goal is to reach a total array sum greater than or equal to k using the minimum number of operations.
Approach 1: Greedy Enumeration with Value Prioritization (O(sqrt(k)) time, O(1) space)
The key observation: copying a large number increases the total sum faster than copying small values. So the strategy is to first grow one element to a target value x using increment operations, then repeatedly copy it until the total sum reaches k. If the maximum element is x, you need x - 1 increments to build it from 1. After that, each copy adds x to the total sum. The number of copies required is ceil(k / x) - 1. The total operations become (x - 1) + (ceil(k / x) - 1). Enumerate possible values of x and choose the minimum cost. Because the optimal balance occurs near sqrt(k), the search space is small. This greedy balancing technique combines ideas from Math, Greedy, and Enumeration.
Approach 2: Dynamic Programming (DP) State Expansion (O(k^2) time, O(k) space)
A more explicit formulation treats the problem as a state transition process. Let dp[s] represent the minimum operations needed to reach a total sum of exactly s. From a given state, you can simulate incrementing any element (increasing the sum by 1) or copying the current maximum value (which increases the sum by that value). The DP explores reachable sums and updates the minimal operation count for each. While this approach models the problem directly, it becomes inefficient for large k because each state may branch into multiple transitions. It is mainly useful for understanding the mechanics of the operations rather than for optimal performance.
Recommended for interviews: The greedy enumeration approach is what interviewers typically expect. It shows you can model the effect of operations mathematically and minimize cost by balancing increments with copies. A brute-force or DP formulation demonstrates understanding of the state space, but the greedy math insight reveals stronger problem-solving skills.
Using a greedy approach, we continuously choose the option that gets us closer to k: duplicating or incrementing. Start with the initial condition nums = [1]. Calculate the sum of the array.
While the sum is less than k, consider which operation provides a greater increase to the sum for fewer operations. Increment if it's easier to duplicate when the sum is higher or duplicate now if doubling helps. Note the numbers of operations performed and stop when the sum meets or exceeds k.
This Python solution uses a while loop that continues until the sum of the array is at least k. Within the loop, it checks if duplicating is an optimal choice at the current step, otherwise, it increments. This is a greedy approach where we choose operations that maximize progress at each step.
Time Complexity: O(log k).
Space Complexity: O(1), as we only use a fixed amount of additional space for variables.
We can create an array 'dp' where each 'dp[i]' stores the minimum number of operations required to reach a sum of 'i'. Start by initializing dp[0] to zero operations since no operations are needed to achieve a sum of zero and dp[1] for initial condition.
Iteratively fill out this array by considering the choices: either incrementing to the next highest sum or duplicating the current sum if it's feasible to do so given the current sum.
This Java solution involves filling a dynamic programming array that tracks the minimum number of operations to achieve each possible sum up to k. It iteratively constructs solutions using previously computed values.
Time Complexity: O(k^2) due to nested loops.
Space Complexity: O(k) to store the DP array.
We should put the copy operation (i.e., operation 2) at the end to reduce the number of operations.
Therefore, we enumerate the number of times a for operation 1 in the range [0, k], then the number of times b for operation 2 is \left\lceil \frac{k}{a+1} \right\rceil - 1. We take the minimum of a+b.
The time complexity is O(k), where k is the input positive integer k. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Greedy Approach with Prioritization | Time Complexity: O(log k). |
| Dynamic Programming (DP) Approach | Time Complexity: O(k^2) due to nested loops. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Enumeration with Target Value | O(sqrt(k)) | O(1) | General case. Optimal for interviews and large k because it minimizes operations using math insight. |
| Dynamic Programming State Simulation | O(k^2) | O(k) | Useful for understanding the operation transitions or when deriving the greedy formula. |
3091. Apply Operations to Make Sum of Array Greater Than or Equal to k | O(1) time | Math | Greedy • Aryan Mittal • 2,493 views views
Watch 9 more video solutions →Practice Apply Operations to Make Sum of Array Greater Than or Equal to k with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor