Apply operations to make sum of array greater than or equal to k

Math Greedy Enumeration

44.2% acceptance

Feb 25, 2026

171

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(k: i32) -> i32 {
    if k == 1 { return 0; }
    // Optimal: increment element to v (costs v-1 ops), then duplicate (v+1-1) ... 
    // Actually: increment base to x (x-1 ops), then duplicate (d times, costs d ops),
    // resulting in x * (d+1) >= k. Total = x - 1 + d.
    // Minimize x - 1 + d s.t. x * (d+1) >= k, x >= 1, d >= 0
    let mut ans = i32::MAX;
    for x in 1..=k {
      // d >= ceil(k/x) - 1
      let d = ((k + x - 1) / x - 1).max(0);
      ans = ans.min((x - 1) + d);
    }
    ans
  }
}