Problem statement

https://leetcode.com/problems/append-k-integers-with-minimal-sum/

Solution

This problem is a bit more difficult that it seems, because we can have k very big. So, one of the possible solutions is the following: Let us sort unique values in A and start with value level = k + 1. For each value in sorted A, we check that this value is less then level: if it is, we update answer: add level and subtract x. Also we start with k * (k + 1)//2 value: sum of all numbers from 1 to k. Imagine example A = [1, 3, 6, 7, 15] and k = 11. Then we start with elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] and we have:

  1. [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]: here we removed 1 and added 12
  2. [2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]: here we removed 3 and added 13.
  3. [2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14]: here we removed 6 and added 14.
  4. [2, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15]: here we removed 7 and added 15.
  5. [2, 4, 5, 8, 9, 10, 11, 12, 13, 14, 16]: here we removed 15 and added 16.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def minimalKSum(self, A, k):
        level, ans = k + 1, 0
        for x in sorted(set(A)):
            if x < level:
                ans += level - x
                level += 1
        return ans + k * (k + 1)//2