Problem

You are given an integer array nums and an integer k. Append k unique positive integers that do not appear in nums to nums such that the resulting total sum is minimum.

Return the sum of the k integers appended to nums.

Examples

Example 1:

1
2
3
4
5

Input: nums = [1,4,25,10,25], k = 2
Output: 5
Explanation: The two unique positive integers that do not appear in nums which we append are 2 and 3.
The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum.
The sum of the two integers appended is 2 + 3 = 5, so we return 5.

Example 2:

1
2
3
4
5

Input: nums = [5,6], k = 6
Output: 25
Explanation: The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8.
The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum. 
The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^8

Solution

Method 1 – Greedy + Gaps

Intuition

To minimize the sum, we should append the smallest missing positive integers not in nums. By sorting and scanning for gaps, we can efficiently find and sum the first k missing numbers.

Approach

  1. Convert nums to a set for O(1) lookups and remove duplicates.
  2. Sort the unique numbers.
  3. Initialize a pointer cur at 1 and a counter for how many numbers we’ve appended.
  4. For each number in the sorted array:
  • While cur is less than the current number and we still need to append numbers:
    • Add cur to the answer, increment cur and the counter.
  • Move cur to one more than the current number.
  1. If we still need to append numbers after the array, keep adding consecutive numbers starting from cur.
  2. Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
   long long minimalKSum(vector<int>& nums, int k) {
      sort(nums.begin(), nums.end());
      long long ans = 0, cur = 1;
      for (int x : nums) {
        if (x < cur) continue;
        if (k == 0) break;
        long long cnt = min((long long)x - cur, (long long)k);
        ans += (cur + cur + cnt - 1) * cnt / 2;
        k -= cnt;
        cur = x + 1;
      }
      if (k > 0) {
        ans += (cur + cur + k - 1) * k / 2;
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func minimalKSum(nums []int, k int) int64 {
   sort.Ints(nums)
   ans, cur := int64(0), int64(1)
   for _, x := range nums {
      if int64(x) < cur {
        continue
      }
      if k == 0 {
        break
      }
      cnt := int64(x) - cur
      if int(cnt) > k {
        cnt = int64(k)
      }
      ans += (cur + cur + cnt - 1) * cnt / 2
      k -= int(cnt)
      cur = int64(x) + 1
   }
   if k > 0 {
      ans += (cur + cur + int64(k) - 1) * int64(k) / 2
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
   public long minimalKSum(int[] nums, int k) {
      Arrays.sort(nums);
      long ans = 0, cur = 1;
      for (int x : nums) {
        if (x < cur) continue;
        if (k == 0) break;
        long cnt = Math.min(x - cur, (long)k);
        ans += (cur + cur + cnt - 1) * cnt / 2;
        k -= cnt;
        cur = x + 1;
      }
      if (k > 0) {
        ans += (cur + cur + k - 1) * k / 2;
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
   fun minimalKSum(nums: IntArray, k: Int): Long {
      nums.sort()
      var ans = 0L
      var cur = 1L
      var rem = k
      for (x in nums) {
        if (x < cur) continue
        if (rem == 0) break
        val cnt = minOf(x - cur, rem.toLong())
        ans += (cur + cur + cnt - 1) * cnt / 2
        rem -= cnt.toInt()
        cur = x.toLong() + 1
      }
      if (rem > 0) {
        ans += (cur + cur + rem - 1) * rem / 2
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
   def minimalKSum(self, nums: list[int], k: int) -> int:
      nums = sorted(set(nums))
      ans = 0
      cur = 1
      for x in nums:
        if x < cur:
           continue
        cnt = min(x - cur, k)
        ans += (cur + cur + cnt - 1) * cnt // 2
        k -= cnt
        cur = x + 1
        if k == 0:
           break
      if k > 0:
        ans += (cur + cur + k - 1) * k // 2
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
   pub fn minimal_k_sum(mut nums: Vec<i32>, mut k: i32) -> i64 {
      nums.sort_unstable();
      nums.dedup();
      let mut ans = 0i64;
      let mut cur = 1i64;
      for &x in &nums {
        if x as i64 < cur { continue; }
        let cnt = (x as i64 - cur).min(k as i64);
        ans += (cur + cur + cnt - 1) * cnt / 2;
        k -= cnt as i32;
        cur = x as i64 + 1;
        if k == 0 { break; }
      }
      if k > 0 {
        ans += (cur + cur + k as i64 - 1) * k as i64 / 2;
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n log n) (for sorting and deduplication)
  • 🧺 Space complexity: O(n) (for storing unique numbers)