Append k integers with minimal sum

Array Math Greedy Sorting

26.9% acceptance

Feb 25, 2026

833

313

You are given an integer array nums and an integer k. Append k unique positive integers that do not appear in nums to minimize the total sum. Return the sum of the k integers appended.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimal_k_sum(nums: Vec<i32>, k: i32) -> i64 {
    let mut nums = nums;
    nums.sort_unstable();
    nums.dedup();
    let mut result = 0i64;
    let mut remaining = k as i64;
    let mut curr = 1i64;
    for n in nums {
      let n = n as i64;
      if curr >= n {
        curr = n + 1;
        continue;
      }
      // Fill from curr to n-1
      let available = n - curr;
      let take = available.min(remaining);
      result += take * (2 * curr + take - 1) / 2;
      remaining -= take;
      curr = n + 1;
      if remaining == 0 {
        break;
      }
    }
    if remaining > 0 {
      result += remaining * (2 * curr + remaining - 1) / 2;
    }
    result
  }
}