LC945. Minimum Increment to Make Array Unique

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        """ time O(NlgN) space O(1)
        """
        low = res  =  0
        for a in sorted(A):
            if low > a :
                res += low - a  
            low = max(low + 1, a + 1)
        return res 

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        """ O(N + KlgK)

        """
        c = collections.Counter(A)
        res = low = 0
        for x in sorted(c):
            if low > x :
                res += (low - x)* c[x]     
            res +=  c[x] * (c[x]-1) // 2 # ??C(cnt,2)
            low = max(low ,x) + c[x]
        return res