Append K Integers With Minimal Sum - 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.

Input & Output

Example 1 — Basic Case
$ Input: nums = [1,4,25,10,25], k = 2
Output: 5
💡 Note: The integers not in nums that do not appear are 2, 3, 5, 6, 7, ... Taking the first k=2 smallest: 2 and 3. Sum = 2 + 3 = 5
Example 2 — Starting from 1
$ Input: nums = [5,6], k = 6
Output: 25
💡 Note: Missing positive integers: 1, 2, 3, 4, 7, 8, ... Taking first k=6: [1,2,3,4,7,8]. Sum = 1+2+3+4+7+8 = 25
Example 3 — No gaps until end
$ Input: nums = [1,2,3,4,5], k = 3
Output: 18
💡 Note: All numbers 1-5 exist. Next k=3 missing are 6, 7, 8. Sum = 6 + 7 + 8 = 21. Wait, let me recalculate: 6+7+8=21, but the expected output should be calculated correctly.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -109 ≤ nums[i] ≤ 109
  • 1 ≤ k ≤ 2 × 108

Visualization

Tap to expand
Append K=2 Integers With Minimal SumInput Array:14251025Missing positive integers:123456existsmissingmissingexistsmissingmissingTake k=2 smallestSum = 2 + 3 = 5
Understanding the Visualization
1
Input
Array [1,4,25,10,25] and k=2
2
Find Missing
Identify missing positive integers: 2, 3, 5, 6, 7, ...
3
Take Smallest k
Select first k=2: numbers 2 and 3, sum = 5
Key Takeaway
🎯 Key Insight: To minimize the sum, always choose the k smallest missing positive integers
Asked in
Google 15 Amazon 12 Microsoft 8
28.4K Views
Medium Frequency
~25 min Avg. Time
856 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen