Skip to main content
Talentd

Apply Operations to Make Sum of Array Greater Than or Equal to k - Solution & Explanation

MediumMathGreedyEnumeration11 min readAsked at: Zscaler, Turing
Practice this problem

Problem Statement

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 1 three times. The resulting array is nums = [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.

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(log k).
Space Complexity: O(1), as we only use a fixed amount of additional space for variables.

Try this approach in the editor →

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.

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.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(k^2) due to nested loops.
Space Complexity: O(k) to store the DP array.

Try this approach in the editor →

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

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Prioritization

Time Complexity: O(log k).
Space Complexity: O(1), as we only use a fixed amount of additional space for variables.

Dynamic Programming (DP) Approach

Time Complexity: O(k^2) due to nested loops.
Space Complexity: O(k) to store the DP array.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Enumeration with Target ValueO(sqrt(k))O(1)General case. Optimal for interviews and large k because it minimizes operations using math insight.
Dynamic Programming State SimulationO(k^2)O(k)Useful for understanding the operation transitions or when deriving the greedy formula.

Video Solution

3091. Apply Operations to Make Sum of Array Greater Than or Equal to k | O(1) time | Math | Greedy • Aryan Mittal • 2,531 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

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 FleetCode
Previous

Add Two Numbers

Next

Reverse Integer