Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.
Return the least number of moves to make every value in A unique.
 
Example 1:
Input: [1,2,2]
Output: 1
Explanation:  After 1 move, the array could be [1, 2, 3].


Example 2:
Input: [3,2,1,2,1,7]
Output: 6
Explanation:  After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

 

Note:

0 <= A.length <= 40000
0 <= A[i] < 40000

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Mathematics

Greedy algorithms

Starter code: class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        

Solutions:
class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		A.sort()
		prev = A[0]
		res = 0
		for num in A[1:]:
			if num <= prev:
				prev += 1
				res += prev - num
			else:
				prev = num
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		n = len(A)
		A.sort()
		tail_num = A[0]
		result = 0
		for i in range(1, n):
			if A[i] > tail_num:
				tail_num = A[i]
			else:
				tail_num += 1
			result += tail_num - A[i]
		return result


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		result = 0
		A.sort()
		for i in range(1, len(A)):
			if A[i - 1] >= A[i]:
				result += A[i - 1] - A[i] + 1
				A[i] = A[i - 1] + 1
		return result


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		count = collections.Counter(A)
		taken = []
		ans = 0
		for x in range(60000):
			if count[x] >= 2:
				taken.extend([x] * (count[x] - 1))
			elif taken and count[x] == 0:
				ans += x - taken.pop()
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		min_num = min(A)
		max_num = max(A)
		count = collections.Counter(A)
		taken = []
		ans = 0
		for x in range(100000):
			if x > max_num and (not taken):
				break
			if count[x] >= 2:
				taken = taken + [x] * (count[x] - 1)
			elif taken and count[x] == 0:
				ans += x - taken.pop()
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		count = collections.Counter(A)
		taken = []
		mv = 0
		for i in range(80000):
			if count[i] > 1:
				taken.extend([i] * (count[i] - 1))
			elif taken and count[i] == 0:
				mv += i - taken.pop()
		return mv


import collections

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		counter = collections.Counter(A)
		res = 0
		for i in range(80000):
			if counter[i] > 1:
				res += counter[i] - 1
				counter[i + 1] += counter[i] - 1
		return res


from collections import Counter

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		hm = dict(Counter(A))
		stack = [k for (k, v) in list(hm.items()) if v > 1]
		ans = 0
		while stack:
			k = stack.pop()
			hm[k + 1] = hm.get(k + 1, 0) + hm[k] - 1
			ans += hm[k] - 1
			hm[k] = 1
			if hm[k + 1] > 1:
				stack.append(k + 1)
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		(N, ans) = (40000, 0)
		(freq, free_slot) = ([0] * N, 0)
		for n in A:
			freq[n] += 1
		for (i, r) in enumerate(freq):
			if r:
				ans += r * (r - 1) // 2 + (free_slot - i) * r
				free_slot += r
			else:
				free_slot = max(free_slot, i + 1)
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		n = len(A)
		A.sort()
		stack = []
		ans = 0
		A.append(A[-1] + n)
		for i in range(1, n + 1):
			if A[i] == A[i - 1]:
				stack.append(A[i])
			else:
				for r in range(1, A[i] - A[i - 1]):
					if stack:
						ans += A[i - 1] + r - stack.pop()
					else:
						break
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		count = collections.Counter(A)
		ans = 0
		waiting = 0
		for x in range(80000):
			if count[x] >= 2:
				waiting += count[x] - 1
				ans -= x * (count[x] - 1)
			elif waiting > 0 and count[x] == 0:
				waiting -= 1
				ans += x
		return ans


class Solution(object):

	def minIncrementForUnique(self, A):
		count = collections.Counter(A)
		taken = []
		ans = 0
		for x in range(100000):
			if count[x] >= 2:
				taken.extend([x] * (count[x] - 1))
			elif taken and count[x] == 0:
				ans += x - taken.pop()
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		count = collections.Counter(A)
		seen = []
		res = 0
		for x in range(100000):
			if count[x] >= 2:
				seen.extend([x] * (count[x] - 1))
			elif seen and count[x] == 0:
				res += x - seen.pop()
		return res


from collections import Counter

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		counts = Counter(A)
		taken = []
		ans = 0
		for num in range(90001):
			num_count = counts[num]
			if num_count >= 2:
				taken.extend([num] * (num_count - 1))
			elif taken and num_count == 0:
				ans += num - taken.pop()
		return ans


from typing import List
from collections import Counter

class Solution:

	def minIncrementForUnique_bruteforce(self, A: List[int]) -> int:
		counts = Counter(A)
		tot_count = 0
		for n in A:
			while counts[n] > 1:
				counts[n] -= 1
				n += 1
				counts[n] += 1
				tot_count += 1
		return tot_count

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		counts = Counter(A)
		count = 0
		taken = []
		for i in range(100000):
			if counts[i] >= 2:
				taken.extend([i for _ in range(counts[i] - 1)])
			elif taken and counts[i] == 0:
				count += i - taken.pop()
		return count


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		f = 80001 * [0]
		max_ = -1
		for i in A:
			f[i] += 1
			max_ = max(max_, i)
		hold = []
		res = 0
		for i in range(max_ + len(A) + 1):
			if hold and f[i] == 0:
				res += i - hold.pop()
			elif f[i] > 1:
				hold = (f[i] - 1) * [i] + hold
		return res


from collections import Counter

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		(cnt, ans) = (Counter(A), 0)
		for i in range(100000):
			if cnt[i] > 1:
				ans += cnt[i] - 1
				cnt[i + 1] += cnt[i] - 1
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		counter = collections.Counter(A)
		taken = []
		result = 0
		for i in range(100000):
			if counter[i] > 1:
				taken.extend([i] * (counter[i] - 1))
			elif taken and counter[i] == 0:
				result += i - taken.pop()
		return result


from collections import Counter

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		c = Counter(A)
		prev = -1
		ans = 0
		for key in sorted(c):
			if key <= prev:
				ans += (0 + c[key] - 1) * c[key] // 2 + c[key] * (prev - key + 1)
				prev = key + c[key] - 1 + prev - key + 1
			else:
				ans += (0 + c[key] - 1) * c[key] // 2
				prev = key + c[key] - 1
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		taken = []
		count = collections.Counter(A)
		moves = 0
		for i in range(100000):
			if count[i] >= 2:
				taken.extend([i] * (count[i] - 1))
			elif taken and count[i] == 0:
				moves += i - taken.pop()
		return moves


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		counts = Counter(A)
		increments = 0
		for num in range(100000):
			count = counts[num]
			if count > 1:
				increments += count - 1
				counts[num] = 1
				if not counts[num + 1]:
					counts[num + 1] = 0
				counts[num + 1] += count - 1
		return increments


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		c = collections.Counter(A)
		mv = 0
		need = 0
		for i in sorted(c):
			mv += max(need - i, 0) * c[i] + c[i] * (c[i] - 1) // 2
			need = max(need, i) + c[i]
		return mv


from collections import Counter

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		c = Counter(A)
		ans = 0
		prev = -1
		for num in sorted(c):
			ans += max(0, prev - num + 1) * c[num] + (c[num] - 1) * c[num] // 2
			prev = num + max(0, prev - num + 1) + (c[num] - 1)
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		a = sorted(A)
		res = 0
		for i in range(0, len(a) - 1):
			if a[i + 1] == a[i]:
				a[i + 1] += 1
				res += 1
			elif a[i + 1] < a[i]:
				k = a[i] - a[i + 1] + 1
				a[i + 1] += k
				res += k
		return res


class Solution:

	def minIncrementForUnique(self, A):
		bar = -1
		res = 0
		for a in sorted(A):
			if a < bar:
				res += bar - a
			bar = max(bar + 1, a + 1)
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		A.append(100000)
		result = taken = 0
		for i in range(1, len(A)):
			if A[i - 1] == A[i]:
				taken += 1
				result -= A[i]
			else:
				give = min(taken, A[i] - A[i - 1] - 1)
				result += give * (give + 1) // 2 + give * A[i - 1]
				taken -= give
		return result
		counter = collections.Counter(A)
		taken = []
		result = 0
		for i in range(100000):
			if counter[i] > 1:
				taken.extend([i] * (counter[i] - 1))
			elif taken and counter[i] == 0:
				result += i - taken.pop()
		return result


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		A.sort()
		next_available = A[0]
		res = 0
		for a in A:
			if a >= next_available:
				next_available = a + 1
			else:
				res += next_available - a
				next_available += 1
		return res


class Solution:

	def minIncrementForUnique(self, A):
		A.sort()
		ans = 0
		for i in range(1, len(A)):
			if A[i] > A[i - 1]:
				continue
			ans += A[i - 1] - A[i] + 1
			A[i] = A[i - 1] + 1
		return ans


class Solution:

	def minIncrementForUnique(self, A):
		res = need = 0
		for i in sorted(A):
			res += max(need - i, 0)
			need = max(need + 1, i + 1)
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		counter = Counter(A)
		to_place = []
		min_key = float('inf')
		for key in counter:
			min_key = min(min_key, key)
			if counter[key] > 1:
				for i in range(counter[key] - 1):
					to_place.append(key)
				counter[key] = 1
		i = min_key
		moves = 0
		to_place.sort(reverse=True)
		while to_place:
			if i not in counter and i > to_place[-1]:
				moves += i - to_place.pop()
			i += 1
		return moves


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		A.append(100000)
		ans = taken = 0
		for i in range(1, len(A)):
			if A[i - 1] == A[i]:
				taken += 1
				ans -= A[i]
			else:
				give = min(taken, A[i] - A[i - 1] - 1)
				ans += give * (give + 1) / 2 + give * A[i - 1]
				taken -= give
		return int(ans)


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		A.sort()
		i = 1
		stack = []
		current = A[0]
		moves = 0
		while i < len(A):
			if A[i] == A[i - 1]:
				stack.append(A[i])
			elif len(stack) > 0:
				for num in range(current + 1, A[i]):
					moves += num - stack.pop()
					if not stack:
						break
			current = A[i]
			i += 1
		while stack:
			moves += current + 1 - stack.pop()
			current += 1
		return moves


import collections

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		(res, need) = (0, 0)
		numCnt = collections.OrderedDict()
		for a in A:
			if a not in numCnt:
				numCnt[a] = 1
			else:
				numCnt[a] += 1
		while numCnt:
			(num, count) = numCnt.popitem(last=False)
			res += max((need - num) * count, 0) + count * (count - 1) // 2
			need = max(num, need) + count
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		ans = 0
		for i in range(1, len(A)):
			if i > 0 and A[i] <= A[i - 1]:
				target = A[i - 1] + 1
				ans += target - A[i]
				A[i] = target
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		count = 0
		A = sorted(A)
		for i in range(len(A) - 1):
			increment = max(0, A[i] - A[i + 1] + 1)
			A[i + 1] += increment
			count += increment
		return count


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if len(A) < 2:
			return 0
		A.sort()
		N = len(A)
		res = 0
		start = 0
		for i in range(1, N):
			if A[i] - A[start] >= i - start:
				start = i
			else:
				res += i - start - (A[i] - A[start])
		return res


from typing import List
from collections import deque, Counter

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		cs = sorted(([n, count] for (n, count) in list(Counter(A).items())))
		stack = deque(cs[::-1])
		numOps = 0
		while stack:
			(n, count) = stack.pop()
			numOps += count - 1
			if count > 1 and stack and (stack[-1][0] == n + 1):
				stack[-1][1] += count - 1
			elif count > 1:
				stack.append([n + 1, count - 1])
		return numOps


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		ans = 0
		(hp, hp2) = ([], [])
		(n, mina, maxa) = (len(A), min(A), max(A))
		seen = set()
		for a in A:
			if a not in seen:
				seen.add(a)
			else:
				heapq.heappush(hp, a)
		for i in range(mina + 1, maxa + n):
			if i not in seen:
				heapq.heappush(hp2, i)
		while hp:
			while hp2[0] <= hp[0]:
				heapq.heappop(hp2)
			ans += heapq.heappop(hp2) - heapq.heappop(hp)
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		A.sort()
		temp = A[0]
		res = 0
		for i in range(1, len(A)):
			if A[i] > temp:
				temp = A[i]
			else:
				res += temp + 1 - A[i]
				temp += 1
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		A_sum = sum(A)
		cnt = 0
		for i in range(1, len(A)):
			if A[i] <= A[i - 1]:
				cnt += A[i] - A[i - 1] + 1
				A[i] = A[i - 1] + 1
		return sum(A) - A_sum


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		A.sort()
		B = [A[0]]
		move = 0
		for a in A[1:]:
			if a <= B[-1]:
				step = B[-1] - a + 1
				move += step
				a = a + step
			B.append(a)
		return move


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		ans = 0
		c = Counter(A)
		backlog = 0
		for i in range(min(A), max(A) + 1):
			if i in c:
				backlog += c[i] - 1
			elif i not in c and backlog:
				ans += i
				backlog -= 1
		ans += sum(range(i + 1, i + 1 + backlog))
		return sum(c.keys()) + ans - sum(A)


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		seen = set()
		replicates = []
		for i in A:
			if i not in seen:
				seen.add(i)
			else:
				replicates.append(i)
		replicates.sort()
		res = 0
		next_candidates = 0
		while replicates:
			num = replicates.pop(0)
			next_candidates = max(next_candidates, num)
			while next_candidates in seen:
				next_candidates += 1
			seen.add(next_candidates)
			res += next_candidates - num
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A = sorted(A)
		ans = 0
		if len(A) == 0:
			return 0
		prev = A[0]
		i = 1
		while i < len(A):
			if A[i] <= prev:
				ans += prev - A[i] + 1
				prev += 1
			else:
				prev = A[i]
			i += 1
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		res = 0
		expect = 0
		for i in sorted(A):
			res += max(expect - i, 0)
			expect = max(i + 1, expect + 1)
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		dup = []
		seen = set()
		for i in A:
			if i not in seen:
				seen.add(i)
			else:
				dup.append(i)
		curr = 0
		j = 0
		i = -1
		ans = 0
		print(seen)
		while j < len(dup):
			if i == dup[j]:
				curr = max(curr, i)
				while curr in seen:
					curr += 1
				seen.add(curr)
				ans += curr - dup[j]
				j += 1
			else:
				i += 1
		return ans


from heapq import heappop, heappush, heapify

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		li = []
		A.sort()
		n = len(A)
		if n == 0:
			return 0
		used = {}
		used[A[0]] = 1
		for i in range(1, n):
			if A[i] == A[i - 1]:
				li.append(A[i])
			else:
				used[A[i]] = 1
		res = 0
		t = A[0]
		for x in li:
			while used.get(t, 0) != 0 or t < x:
				t += 1
			used[t] = 1
			res += t - x
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:

		def find(x):
			root[x] = find(root[x] + 1) if x in root else x
			return root[x]
		root = {}
		return sum((find(i) - i for i in A))


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		roots = {}

		def find(k):
			roots[k] = k if k not in roots else find(roots[k] + 1)
			return roots[k]
		return sum((find(a) - a for a in A))


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		a = sorted(A)
		b = []
		if a == sorted(set(a)):
			return 0
		res = 0
		for i in range(0, len(a) - 1):
			print('now: ', a[i], a[i + 1])
			if a[i + 1] == a[i]:
				a[i + 1] += 1
				res += 1
			elif a[i + 1] < a[i]:
				k = a[i] - a[i + 1] + 1
				a[i + 1] += k
				res += k
		print(b)
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		diff = 0
		stack = []
		c = Counter(A)
		for i in range(min(c.keys()), max(c.keys()) + 1):
			if i in c:
				stack += [i] * (c[i] - 1)
			elif i not in c and stack:
				diff += i - stack.pop()
		return diff + sum(range(i + 1, i + 1 + len(stack))) - sum(stack)


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		ans = 0
		for (i, x) in enumerate(A):
			if i >= 1:
				if A[i] <= A[i - 1]:
					ans += A[i - 1] - A[i] + 1
					A[i] = A[i - 1] + 1
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if len(A) < 2:
			return 0
		A.sort()
		(ans, last) = (0, A[0] - 1)
		for n in A:
			if n > last:
				last = n
			else:
				ans += last - n + 1
				last += 1
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A or len(A) == 1:
			return 0
		ans = 0
		A.sort()
		for i in range(1, len(A)):
			if A[i - 1] >= A[i]:
				gap = abs(A[i - 1] - A[i]) + 1
				A[i] += gap
				ans += gap
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		n = len(A)
		if n < 2:
			return 0
		A.sort()
		avails = deque()
		for i in range(1, n):
			if A[i] > A[i - 1] + 1:
				avails.append([A[i - 1] + 1, A[i]])
			if i == n - 1:
				avails.append([A[i] + 1, A[i] + 2])
		(l, r) = avails.popleft()
		nexts = deque(range(l, r))
		r = nexts.popleft()
		pre = A[0]
		res = 0
		for i in range(1, n):
			if A[i] == pre:
				while r <= A[i]:
					if nexts:
						r = nexts.popleft()
					elif avails:
						(l, r) = avails.popleft()
						nexts = deque(range(l, r))
						r = nexts.popleft()
					else:
						r += 1
				res += r - A[i]
				A[i] = r
				if nexts:
					r = nexts.popleft()
				elif avails:
					(l, r) = avails.popleft()
					nexts = deque(range(l, r))
					r = nexts.popleft()
				else:
					r += 1
			else:
				pre = A[i]
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		n = {}

		def find(x):
			n[x] = find(n[x] + 1) if x in n else x
			return n[x]
		return sum((find(a) - a for a in A))


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		n = {}
		ans = 0

		def find(j):
			n[j] = find(n[j] + 1) if j in n else j
			return n[j]
		for i in A:
			ans += find(i) - i
		return ans


class Solution:

	def minIncrementForUnique(self, A):
		root = {}

		def find(x):
			root[x] = find(root[x] + 1) if x in root else x
			return root[x]
		return sum((find(a) - a for a in A))


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A = sorted(A)
		if not A:
			return 0
		k = A[0]
		moves = 0
		for i in range(1, len(A)):
			if A[i] <= k:
				moves += k + 1 - A[i]
				A[i] = k + 1
			k = A[i]
		return moves


class Solution:

	def minIncrementForUnique(self, arr: List[int]) -> int:
		if not arr:
			return 0
		arr.sort()
		(s, ans) = (arr[0], 0)
		for i in arr:
			ans += max(0, s - i)
			s = max(s + 1, i + 1)
		return ans


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if len(A) == 0 or len(A) == 1:
			return 0
		A.sort()
		cnt = 0
		for i in range(1, len(A)):
			if A[i - 1] >= A[i]:
				temp = A[i]
				A[i] = A[i - 1] + 1
				cnt += A[i] - temp
		return cnt


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		ret = 0
		for i in range(1, len(A)):
			p = A[i - 1]
			c = A[i]
			if p >= c:
				ret += p - c + 1
				A[i] = p + 1
		return ret


from collections import defaultdict

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		H = defaultdict(int)
		for a in A:
			H[a] += 1
		V = sorted(H.keys())
		ans = 0
		while True:
			if len(H) == 0:
				return ans
			elif len(H) == 1:
				v = min(H.keys())
				ans += (H[v] - 1) * H[v] // 2
				del H[v]
				del V[0]
			else:
				(v1, v2) = (V[0], V[1])
				if v1 + H[v1] - 1 < v2:
					ans += (H[v1] - 1) * H[v1] // 2
					del H[v1]
					del V[0]
				else:
					ans += (v2 - v1 - 1) * (v2 - v1) // 2
					ans += (H[v1] - v2 + v1) * (v2 - v1)
					H[v2] += H[v1] - v2 + v1
					del H[v1]
					del V[0]


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		A.sort()
		results = 0
		prev = None
		for num in A:
			if prev != None and num <= prev:
				results += prev + 1 - num
				prev = prev + 1
			else:
				prev = num
		return results


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A = sorted(A)
		nums = set()
		move = 0
		prev = -1
		for i in range(len(A)):
			cur_num = A[i]
			if cur_num <= prev:
				cur_num = prev + 1
			while cur_num in nums:
				cur_num += 1
			nums.add(cur_num)
			move += cur_num - A[i]
			prev = cur_num
		return move


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		step = curr = 0
		for e in sorted(A):
			step += max(curr - e, 0)
			curr = max(curr, e) + 1
		return step


from collections import defaultdict

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		histogram = defaultdict(int)
		for num in A:
			histogram[num] += 1
		count = 0
		taken = []
		for num in range(0, 100000):
			if num in histogram and histogram[num] > 1:
				taken += [num] * (histogram[num] - 1)
			elif taken and num not in histogram:
				count += num - taken.pop()
		return count


from collections import defaultdict

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		to_merge = []
		moves = 0
		for i in range(1, len(A)):
			if A[i] == A[i - 1]:
				to_merge.append(A[i])
			elif to_merge:
				j = A[i - 1]
				for j in range(A[i - 1] + 1, A[i]):
					m = to_merge.pop(0)
					moves += j - m
					if not to_merge:
						break
		if to_merge:
			j = A[-1] + 1
			while to_merge:
				m = to_merge.pop(0)
				moves += j - m
				j += 1
		return moves


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if A == []:
			return 0
		else:
			A.sort()
			pre_item = A[0]
			moves = 0
			for i in range(1, len(A)):
				cur_item = A[i]
				if A[i] < pre_item or A[i] == pre_item:
					moves = moves + pre_item + 1 - A[i]
					A[i] = pre_item + 1
				pre_item = A[i]
			return moves


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		A.sort()
		rez = 0
		for index in range(1, len(A)):
			if A[index - 1] >= A[index]:
				rez += A[index - 1] - A[index] + 1
				A[index] = A[index - 1] + 1
		return rez


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		if not A:
			return 0
		repeat = collections.deque()
		A = sorted(A)
		for (i, v) in enumerate(A):
			if i and v == A[i - 1]:
				repeat.append(v)
		slots = sorted(list(set(list(range(A[0], A[-1] + 1))) - set(A)))
		res = 0
		for i in slots:
			if repeat and i > repeat[0]:
				res += i - repeat[0]
				repeat.popleft()
		return res - sum(repeat) + sum([i for i in range(A[-1] + 1, A[-1] + 1 + len(repeat))])


from collections import defaultdict

class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		count_for_val = defaultdict(lambda : 0)
		dups = set()
		for i in A:
			count_for_val[i] += 1
			if count_for_val[i] > 1:
				dups.add(i)
		output = 0
		dups = sorted(dups)
		if not len(dups):
			return 0
		orig = dups[0]
		for dup in dups:
			count = count_for_val[dup] - 1
			while count > 0:
				orig += 1
				if orig > dup and orig not in count_for_val:
					count_for_val[orig] = 1
					output = output + (orig - dup)
					count -= 1
		return output


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		step = 0
		if not A or len(A) == 1:
			return step
		prev = float('-inf')
		nums = sorted(A)
		for e in nums:
			if e <= prev:
				step += prev - e + 1
				prev += 1
			else:
				prev = e
		return step


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		c = Counter(A)
		print(c)
		res = need = 0
		for i in sorted(A):
			res += max(need - i, 0)
			need = max(need + 1, i + 1)
		return res


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		dic = dict(collections.Counter(A))
		sortedDic = sorted(list(dic.items()), key=lambda x: x[0])
		result = 0
		while sortedDic:
			(num, freq) = sortedDic.pop(0)
			if freq > 1:
				diff = freq - 1
				if sortedDic and sortedDic[0][0] == num + 1:
					sortedDic[0] = (num + 1, diff + sortedDic[0][1])
				else:
					sortedDic.insert(0, (num + 1, diff))
				result += diff
		return result


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		count = collections.Counter(A)
		to_move = []
		num_moves = 0
		end = 50000
		for i in range(end):
			if count[i] >= 2:
				to_move.extend([i] * (count[i] - 1))
			elif to_move and count[i] == 0:
				num_moves += i - to_move.pop()
		return num_moves


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		count = collections.Counter(A)
		taken = []
		moves = 0
		for i in range(45000):
			c = count[i]
			if c >= 2:
				taken += (c - 1) * [i]
			elif len(taken) > 0 and c == 0:
				moves += i - taken.pop()
		return moves


class Solution:

	def minIncrementForUnique(self, A: List[int]) -> int:
		cnt = [0 for i in range(80001)]
		(minv, ans, n) = (40001, 0, len(A))
		for i in A:
			cnt[i] += 1
			minv = min(minv, i)
		for i in range(minv, 80001):
			if not n:
				break
			if cnt[i] > 1:
				cnt[i + 1] += cnt[i] - 1
				ans += cnt[i] - 1
			if cnt[i] == 1:
				n -= 1
		return ans