2195. Append K Integers With Minimal Sum LeetCode Solution

Last updated: February 26, 2025

In this guide, you will get 2195. Append K Integers With Minimal Sum LeetCode Solution with the best time and space complexity. The solution to Append K Integers With Minimal Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Append K Integers With Minimal Sum solution in C++
Append K Integers With Minimal Sum solution in Java
Append K Integers With Minimal Sum solution in Python
Additional Resources

2195. Append K Integers With Minimal Sum LeetCode Solution image

Problem Statement of Append K Integers With Minimal Sum

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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

2195. Append K Integers With Minimal Sum LeetCode Solution in C++

class Solution {
 public:
  long long minimalKSum(vector<int>& nums, int k) {
    long ans = 0;
    nums.push_back(0);
    ranges::sort(nums);

    for (int i = 0; i + 1 < nums.size(); ++i) {
      if (nums[i] == nums[i + 1])
        continue;
      const int l = nums[i] + 1;
      const int r = min(nums[i] + k, nums[i + 1] - 1);
      ans += static_cast<long>(l + r) * (r - l + 1) / 2;
      k -= r - l + 1;
      if (k == 0)
        return ans;
    }

    if (k > 0) {
      const int l = nums.back() + 1;
      const int r = nums.back() + k;
      ans += static_cast<long>(l + r) * (r - l + 1) / 2;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2195. Append K Integers With Minimal Sum LeetCode Solution in Java

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

    if (nums[0] > 1) {
      final int l = 1;
      final int r = Math.min(k, nums[0] - 1);
      ans += (long) (l + r) * (r - l + 1) / 2;
      k -= r - l + 1;
      if (k == 0)
        return ans;
    }

    for (int i = 0; i + 1 < nums.length; ++i) {
      if (nums[i] == nums[i + 1])
        continue;
      final int l = nums[i] + 1;
      final int r = Math.min(nums[i] + k, nums[i + 1] - 1);
      ans += (long) (l + r) * (r - l + 1) / 2;
      k -= r - l + 1;
      if (k == 0)
        return ans;
    }

    if (k > 0) {
      final int l = nums[nums.length - 1] + 1;
      final int r = nums[nums.length - 1] + k;
      ans += (long) (l + r) * (r - l + 1) / 2;
    }

    return ans;
  }
}
// code provided by PROGIEZ

2195. Append K Integers With Minimal Sum LeetCode Solution in Python

class Solution:
  def minimalKSum(self, nums: list[int], k: int) -> int:
    ans = 0
    nums.append(0)
    nums.sort()

    for a, b in zip(nums, nums[1:]):
      if a == b:
        continue
      l = a + 1
      r = min(a + k, b - 1)
      ans += (l + r) * (r - l + 1) // 2
      k -= r - l + 1
      if k == 0:
        return ans

    if k > 0:
      l = nums[-1] + 1
      r = nums[-1] + k
      ans += (l + r) * (r - l + 1) // 2

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents