Skip to content

Practice Apply Operations to Make Sum of Array Greater Than or Equal to k

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#3091
LeetCode Problem

Apply Operations to Make Sum of Array Greater Than or Equal to k

Problem Statement

Start with nums = [1]. In one operation, either increase any existing element by 1 or append a copy of any existing element. Find the fewest operations needed for the array sum to reach or exceed the positive integer k. Practice approach: Try a final repeated value v. Reaching it costs v-1 increments, and producing enough copies costs ceil(k/v)-1 duplications. Minimize their sum for 1 <= v <= k. This direct enumeration takes O(k) time and O(1) space; it returns zero when k is one.

Source: Apply Operations to Make Sum of Array Greater Than or Equal to k on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
k = 11
Output
5

# Example 2

Input
k = 1
Output
0

Constraints

1 <= k <= 100000

How to solve Apply Operations to Make Sum of Array Greater Than or Equal to k

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

All increments should precede all duplications, since raising a value before copying it multiplies the benefit, and every copy should be of the single largest value. The final array is c copies of some v, costing (v - 1) + (c - 1) with c = ceil(k / v), and v * c reaching k is cheapest when v and c are both near sqrt(k).

Why brute force is not enough

Searching over interleavings of increments and copies, or a breadth-first search over array states, explodes combinatorially even for moderate k; the structural observation collapses the search to a single parameter.

Approach

  1. Argue the shape of an optimal sequence: moving an increment ahead of a copy never raises the operation count or lowers the sum, so some optimal solution does all increments first and then duplicates only the maximum.
  2. With that shape, the final array is c copies of v, built with v - 1 increments and c - 1 duplications; the smallest valid c is ceil(k / v).
  3. Enumerate v from 1 to k, evaluate (v - 1) + ceil(k / v) - 1, and keep the minimum; after checking v, the best cost over all final values at most v is known.
  4. Optionally restrict v to a small window around sqrt(k), where the convex cost v + k / v is minimized. For k = 1 the formula with v = 1 correctly gives 0.

Walkthrough of Example 1

k = 11 → 5

  1. k = 11, v = 1: 0 increments and ceil(11 / 1) - 1 = 10 copies, cost 10.
  2. v = 2: 1 increment and 5 copies, cost 6.
  3. v = 3: 2 increments and 3 copies, cost 5, giving [3, 3, 3, 3] with sum 12.
  4. v = 4: 3 increments and 2 copies, cost 5, giving [4, 4, 4] with sum 12.
  5. v = 5: 4 increments and 2 copies, cost 6, and larger v only grows the increment term. The minimum is 5.

Time and space

Time O(sqrt(k)) · Space O(1). Checking final values v within a constant window of sqrt(k), or stopping once v passes sqrt(k) because the cost is then nondecreasing, bounds the loop; the full O(k) enumeration is also acceptable for k up to 10^5. Only a few scalars are kept.

Interview pitfalls

  • Computing copies as k / v with integer division and not rounding up, which undershoots the sum whenever v does not divide k.
  • Counting the original element as a duplication; c copies need only c - 1 operations.
  • Returning a positive count for k = 1, although [1] already qualifies.
  • Checking only floor(sqrt(k)) or ceil(sqrt(k)); the ceiling can shift the optimum a step or two, so test a small neighborhood or the whole range.

Follow-up questions interviewers ask

  • How does the formula change if increments cost a and duplications cost b?
  • What if a duplication copied the entire current array rather than one element?
  • Can you prove the exchange argument that increments precede duplications in some optimal sequence?

Further reading on the technique: Inequality of arithmetic and geometric means

Related LeetCode Problems

Practice more problems similar to Apply Operations to Make Sum of Array Greater Than or Equal to k.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.