# Append K Integers With Minimal Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/append-k-integers-with-minimal-sum)
Canonical: https://scaleengineer.com/dsa/problems/append-k-integers-with-minimal-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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`.

**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 <= 105`
* `1 <= nums[i] <= 109`
* `1 <= k <= 108`

# Approaches
## Brute-force Simulation with a Set
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.
**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`.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient for large values of `k`, as the main loop's iterations depend on `k`.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Create a `HashSet` and populate it with all the numbers from the input array `nums`. This allows for average O(1) time complexity for checking if a number exists.
*   Initialize a `long` variable `sum` to 0 to store the sum of the appended integers, and an integer `count` to 0.
*   Initialize a `long` variable `currentNum` to 1. This will be the candidate integer to append.
*   Start a loop that continues as long as `count < k`.
*   Inside the loop, check if `currentNum` is present in the `HashSet`.
*   If `currentNum` is *not* in the set, it's a valid number to append. Add `currentNum` to `sum` and increment `count`.
*   Increment `currentNum` in every iteration to check the next positive integer.
*   Once the loop finishes (i.e., `count` reaches `k`), return the total `sum`.

## Sorting and Calculating Gaps
A more efficient approach is to sort the `nums` array first. By sorting, we can easily identify consecutive blocks of numbers (gaps) that are missing. We can then calculate the sum of numbers in these gaps efficiently using the arithmetic series sum formula, avoiding a one-by-one check up to `k`.
**Time:** O(n log n), where n is the length of `nums`. The dominant operation is sorting the array. The subsequent loop runs in O(n). · **Space:** O(log n) or O(n), depending on the space complexity of the sorting algorithm used by the language's standard library.
**Pros:** Significantly more efficient than the brute-force approach, especially for large `k`.; Avoids iterating up to `k` by calculating sums of missing number ranges.
**Cons:** The sorting step has a time complexity of O(n log n), which is not as optimal as a linear time solution.
### Explanation
Instead of checking every number from 1 upwards, we can leverage the structure of the input. By sorting `nums`, we can process the existing numbers in order. We keep track of the next positive integer we expect to add, let's call it `nextMissing` (initially 1). As we iterate through the sorted `nums`, if we encounter a number `num` that is greater than `nextMissing`, we know all integers in the range `[nextMissing, num - 1]` are available. We can add up to `k` of these numbers, calculate their sum in O(1) using the arithmetic series formula, and update `k` and `nextMissing` accordingly. If `k` is not yet zero after iterating through all of `nums`, we add the remaining required numbers, which will be consecutive integers starting from the final `nextMissing` value.

```java
import java.util.Arrays;

class Solution {
    public long minimalKSum(int[] nums, int k) {
        Arrays.sort(nums);
        long sum = 0;
        long k_long = k;
        long nextMissing = 1;

        for (int num : nums) {
            if (k_long == 0) {
                break;
            }
            // Skip numbers smaller than our current search point or duplicates
            if (num < nextMissing) {
                continue;
            }
            if (num == nextMissing) {
                nextMissing++;
                continue;
            }

            // Gap found: from nextMissing to num - 1
            long countInGap = num - nextMissing;
            long canAdd = Math.min(k_long, countInGap);
            
            long start = nextMissing;
            long end = nextMissing + canAdd - 1;
            sum += (end + start) * canAdd / 2;
            
            k_long -= canAdd;
            nextMissing = (long)num + 1;
        }

        // If k is still not zero, add remaining numbers
        if (k_long > 0) {
            long start = nextMissing;
            long end = nextMissing + k_long - 1;
            sum += (end + start) * k_long / 2;
        }

        return sum;
    }
}
```
### Algorithm
*   Sort the `nums` array in non-decreasing order.
*   Initialize a `long` variable `sum` to 0, and a `long` variable `nextMissing` to 1 (representing the next smallest positive integer we are looking for).
*   Iterate through the sorted `nums` array, skipping duplicates.
*   For each unique `num` in `nums`:
    *   If `num > nextMissing`, there is a gap of missing numbers between `nextMissing` and `num - 1`.
    *   Calculate how many numbers we can add from this gap, which is `min(k, num - nextMissing)`.
    *   Calculate the sum of these numbers using the arithmetic series sum formula and add it to the total `sum`.
    *   Decrement `k` by the count of numbers added.
    *   If `k` becomes 0, break the loop.
*   Update `nextMissing` to be `num + 1`.
*   After the loop, if `k` is still positive, add the sum of the next `k` integers starting from `nextMissing`.
*   Return the final `sum`.

## Mathematical Approach with a Set
This is the most optimal approach. The idea is to assume we are adding the first `k` positive integers (1, 2, ..., k) and calculate their sum. Then, we correct this sum. For any number `num` from the input array `nums` that is less than or equal to `k`, we must have wrongly included it. So, we subtract `num` from our sum and add the next available integer greater than `k` that is not in `nums`.
**Time:** O(n), where n is the length of `nums`. Building the `HashSet` takes O(n). The loop iterates through unique elements (at most n). The inner `while` loop's total work is bounded because `nextAvailable` only ever increases, making the overall complexity linear. · **Space:** O(n), where n is the number of unique elements in `nums`, for storing the `HashSet`.
**Pros:** Achieves the best time complexity of O(n).; Conceptually elegant by starting with an ideal sum and making corrections.
**Cons:** Uses O(n) extra space for the HashSet, which might be a concern for very large inputs with strict memory limits.
### Explanation
This approach starts with a powerful assumption: the `k` integers to be added are `1, 2, ..., k`. The sum is easily calculated as `k*(k+1)/2`. This assumption is only wrong if some of these numbers (from 1 to `k`) are already present in `nums`. We can identify these conflicting numbers by putting all `nums` into a `HashSet`. We then iterate through the unique numbers in `nums`. If a number `num` is less than or equal to `k`, we must remove it from our sum and add a substitute. The smallest possible substitute is the smallest integer greater than `k` that is not in `nums`. We find this by starting a search from `k+1` and incrementing until we find a number not in the `HashSet`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long minimalKSum(int[] nums, int k) {
        long sum = (long)k * (k + 1) / 2;
        
        Set<Integer> uniqueNums = new HashSet<>();
        for (int num : nums) {
            uniqueNums.add(num);
        }
        
        long nextAvailable = k + 1;
        for (int num : uniqueNums) {
            if (num <= k) {
                sum -= num;
                while (uniqueNums.contains((int)nextAvailable)) {
                    nextAvailable++;
                }
                sum += nextAvailable;
                nextAvailable++;
            }
        }
        
        return sum;
    }
}
```
### Algorithm
*   Calculate the ideal sum of the first `k` positive integers: `sum = (long)k * (k + 1) / 2`.
*   Create a `HashSet` of the unique elements from `nums` for O(1) average time lookups.
*   Initialize `nextAvailable = k + 1`. This is the first candidate for a replacement number.
*   Iterate through the unique numbers (`num`) in the `HashSet`.
*   If `num <= k`, it conflicts with our initial assumption.
    *   Subtract `num` from `sum`.
    *   Find the next available replacement: `while` the `HashSet` contains `nextAvailable`, increment `nextAvailable`.
    *   Add the found `nextAvailable` to `sum`.
    *   Increment `nextAvailable` to prepare for the next potential replacement.
*   Return the final `sum`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int: nums . append(0) nums . append(2 * 10 ** 9) nums . sort() ans = 0 for a, b in pairwise(nums): n = min(k, b - a - 1) if n <= 0: continue k -= n ans += (a + 1 + a + n) * n // 2 if k == 0: break return ans

```

### CPP

```cpp
class Solution {
public:
  long long minimalKSum(vector<int> &nums, int k) {
    nums.push_back(0);
    nums.push_back(2e9);
    sort(nums.begin(), nums.end());
    long long ans = 0;
    for (int i = 1; i < nums.size(); ++i) {
      int a = nums[i - 1], b = nums[i];
      int n = min(k, b - a - 1);
      if (n <= 0)
        continue;
      k -= n;
      ans += 1ll * (a + 1 + a + n) * n / 2;
      if (k == 0)
        break;
    }
    return ans;
  }
};

```