Append K Integers With Minimal Sum
MedPrompt
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.
Example 1:
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:
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 <= 1051 <= nums[i] <= 1091 <= k <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
This approach simulates the process directly. We want to find the k smallest positive integers not present in nums. We can use a HashSet for efficient lookups of numbers in nums. We then iterate upwards from 1, checking each number. If a number is not in the set, we add it to our sum and decrement k. We continue this until we have found k numbers.
Algorithm
- Create a
HashSetand populate it with all the numbers from the input arraynums. This allows for average O(1) time complexity for checking if a number exists. - Initialize a
longvariablesumto 0 to store the sum of the appended integers, and an integercountto 0. - Initialize a
longvariablecurrentNumto 1. This will be the candidate integer to append. - Start a loop that continues as long as
count < k. - Inside the loop, check if
currentNumis present in theHashSet. - If
currentNumis not in the set, it's a valid number to append. AddcurrentNumtosumand incrementcount. - Increment
currentNumin every iteration to check the next positive integer. - Once the loop finishes (i.e.,
countreachesk), return the totalsum.
Walkthrough
The core idea is to iterate through positive integers starting from 1 and, for each integer, check if it's already in the nums array. To make this check efficient, we first store all elements of nums in a HashSet. We maintain a running sum and a count of numbers we've decided to append. We keep checking and adding numbers until we have found k of them.
import java.util.HashSet;import java.util.Set; class Solution { public long minimalKSum(int[] nums, int k) { Set<Integer> numSet = new HashSet<>(); for (int num : nums) { numSet.add(num); } long sum = 0; int count = 0; long currentNum = 1; while (count < k) { if (!numSet.contains((int)currentNum)) { sum += currentNum; count++; } currentNum++; } return sum; }}Complexity
Time
O(n + k), where n is the length of `nums`. It takes O(n) to build the set. The `while` loop might run up to `n + k` times in the worst-case scenario (e.g., if `nums` contains `1, 2, ..., n`). Given `k` can be up to `10^8`, this will likely result in a Time Limit Exceeded (TLE) error.
Space
O(n), where n is the number of elements in `nums`. This space is used to store the `HashSet`.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient for large values of
k, as the main loop's iterations depend onk.
Solutions
Solution
class Solution {public long minimalKSum(int[] nums, int k) { int[] arr = new int[nums.length + 2]; arr[arr.length - 1] = (int)2 e9; for (int i = 0; i < nums.length; ++i) { arr[i + 1] = nums[i]; } Arrays.sort(arr); long ans = 0; for (int i = 1; i < arr.length; ++i) { int a = arr[i - 1], b = arr[i]; int n = Math.min(k, b - a - 1); if (n <= 0) { continue; } k -= n; ans += (long)(a + 1 + a + n) * n / 2; if (k == 0) { break; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.