Apply Operations to Make Sum of Array Greater Than or Equal to k solution and explanation
9 more videos on this problem
3091. Apply Operations to Make Sum of Array Greater Than or Equal to k | O(1) time | Math | GreedyAryan Mittal · 22:21 · 2K views
100228 Apply Operations to Make Sum of Array Greater Than or Equal to k | leetcode | solved || javaSsquare · 1:28 · 1K views
3091 Apply Operations to Make Sum of Array Greater Than or Equal to k || Maths ✅ || GreedyAyush Rao · 8:12 · 1K views
Apply Operations to Make Sum of Array Greater Than or Equal to k - LEETCODE WEEKLY CONTEST 390Joyjit Codes · 3:38 · 776 views
3091. Apply Operations to Make Sum of Array Greater Than or Equal to k (Leetcode Medium)Programming Live with Larry · 10:38 · 371 views
3091. Apply Operations to Make Sum of Array Greater Than or Equal to k | Weekly Contest 390 | C++Priyanshi Porwal · 14:44 · 335 views
Leetcode 3091: Apply Operations to Make Sum of Array Greater Than or Equal to kAlgorithms Casts · 9:38 · 190 views
3091. Apply Operations to Make Sum of Array Greater Than or Equal to k | Leetcode ContestBatchMates · 6:44 · 20 views
Leetcode weekly-contest-390 | 3091 Apply Operations to Make Sum of Array Greater Than or Equal to kCodingVerse · 32:11 · 17 views
Apply Operations to Make Sum of Array Greater Than or Equal to k LeetCode Contest 390letuslearn · 0:34 · 10 views
The problem
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):
- Choose any element in the array and increase its value by
1. - Duplicate any element in the array and add it to the end of the array.
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]:
- Increase the element by
1three times. The resulting array isnums = [4]. - Duplicate the element two times. The resulting array is
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 <= 105
Approach overview
Problem 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.
Approach 1: Greedy Approach with Prioritization
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.
def min_operations(k):
nums = [1]
cur_sum = 1
operations = 0
while cur_sum < k:
if (cur_sum * 2) <= k:
cur_sum *= 2
operations += 1
else:
increase = k - cur_sum
operations += increase
cur_sum += increase
return operations
# Example usage
print(min_operations(11)) # Output: 5
print(min_operations(1)) # Output: 0#include <iostream>
using namespace std;
int minOperations(int k) {
int cur_sum = 1;
int operations = 0;
while (cur_sum < k) {
if (cur_sum * 2 <= k) {
cur_sum *= 2;
operations++;
} else {
operations += (k - cur_sum);
cur_sum = k;
}
}
return operations;
}
int main() {
cout << minOperations(11) << endl; // Output: 5
cout << minOperations(1) << endl; // Output: 0
return 0;
}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.
Approach 2: Dynamic Programming (DP) Approach
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.
public class MinOperations {
public static int minOperations(int k) {
int[] dp = new int[k + 1];
dp[1] = 0; // Starting with [1]
for (int i = 2; i <= k; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 1; j < i; j++) {
if (j * 2 <= i) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
dp[i] = Math.min(dp[i], dp[i-1] + 1);
}
return dp[k];
}
public static void main(String[] args) {
System.out.println(minOperations(11)); // Output: 5
System.out.println(minOperations(1)); // Output: 0
}
}using System;
public class MinOperations {
public static int MinOperations(int k) {
int[] dp = new int[k + 1];
for (int i = 2; i <= k; i++) {
dp[i] = int.MaxValue;
for (int j = 1; j < i; j++) {
if (j * 2 <= i) {
dp[i] = Math.Min(dp[i], dp[j] + 1);
}
}
dp[i] = Math.Min(dp[i], dp[i-1] + 1);
}
return dp[k];
}
public static void Main(string[] args) {
Console.WriteLine(MinOperations(11)); // Output: 5
Console.WriteLine(MinOperations(1)); // Output: 0
}
}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.
Approach 3: Enumeration
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).
function minOperations(k: number): number {
let ans = k;
for (let a = 0; a < k; ++a) {
const x = a + 1;
const b = Math.ceil(k / x) - 1;
ans = Math.min(ans, a + b);
}
return ans;
}func minOperations(k int) int {
ans := k
for a := 0; a < k; a++ {
x := a + 1
b := (k+x-1)/x - 1
ans = min(ans, a+b)
}
return ans
}impl Solution {
pub fn min_operations(k: i32) -> i32 {
let mut ans = k;
for a in 0..k {
let x = a + 1;
let b = (k + x - 1) / x - 1;
ans = ans.min(a + b);
}
ans
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Apply Operations to Make Sum of Array Greater Than or Equal to k easy or hard?
The problem is rated Medium because the operations themselves are simple but the optimal solution requires a mathematical observation. Many first attempts simulate operations or use DP, while the intended solution uses a greedy enumeration formula.
Apply Operations to Make Sum of Array Greater Than or Equal to k Python/Java solution
In Python or Java, iterate over possible values of x (the largest element after increments). For each x, compute operations = (x - 1) + (ceil(k / x) - 1) and track the minimum. The implementation uses simple loops and integer arithmetic.
How to solve Apply Operations to Make Sum of Array Greater Than or Equal to k in O(n)?
The problem is typically solved in O(sqrt(k)) rather than O(n). The idea is to enumerate the target value x of the largest element, compute increments needed (x-1), and then calculate copies needed ceil(k/x)-1. The minimum total operations across all candidates gives the answer.
What is the best approach for Apply Operations to Make Sum of Array Greater Than or Equal to k?
The optimal approach is a greedy math strategy that balances increments and copy operations. First increase one element to a value x using x-1 increments, then copy that value until the total sum reaches k. The cost becomes (x - 1) + (ceil(k / x) - 1). Enumerating x around sqrt(k) finds the minimum efficiently.
Is Apply Operations to Make Sum of Array Greater Than or Equal to k asked at Google/Amazon/Meta?
This style of problem appears in interviews at large tech companies because it tests mathematical reasoning and greedy optimization. Variants involving operation cost balancing and array growth are common in Google, Amazon, and Meta coding interviews.
What data structure is used in Apply Operations to Make Sum of Array Greater Than or Equal to k?
No complex data structure is required. The optimal solution relies mainly on mathematical reasoning and simple enumeration. Only a few integer variables are needed to compute increments, copies, and the resulting sum.
What is the time complexity of Apply Operations to Make Sum of Array Greater Than or Equal to k?
The optimized greedy solution runs in O(sqrt(k)) time and O(1) space because only a small range of candidate values for the maximum element needs to be tested. A naive dynamic programming simulation can take up to O(k^2) time and O(k) space.