Skip to content

2195. Append K Integers With Minimal Sum

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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