Given an array arr[ ] of N elements, your task is to find the minimum number of increment operations required to make all the elements of the array unique. ie- no value in the array should occur more than once. In an operation a value can be incremented by 1 only.
Example 1:
Input:
N = 3
arr[] = {1, 2, 2}
Output:
1
Explanation:
If we increase arr[2] by 1 then the resulting 
array becomes {1, 2, 3} and has all unique values.
Hence, the answer is 1 in this case.
Example 2:
Input: 
N = 4
arr[] = {1, 1, 2, 3}
Output:
3
Explanation: 
If we increase arr[0] by 3, then all array
elements will be unique. Hence, the answer 
is 3 in this case.
Your Task:
You dont need to read input or print anything. Complete the function minIncrements() which takes the array arr[ ] and its size N as the input parameters, and returns the minimum increment operations required to make all elements of the array unique.
Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5 }
1 ≤ arr[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def minIncrements(self, arr, N): 

        # Code here

Solutions:
class Solution:

	def minIncrements(self, arr, N):
		c = 0
		arr.sort()
		for i in range(1, len(arr)):
			if arr[i] <= arr[i - 1]:
				c += arr[i - 1] + 1 - arr[i]
				arr[i] = arr[i - 1] + 1
		return c


class Solution:

	def minIncrements(self, arr, N):
		res = 0
		arr.sort()
		m = arr[0]
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				res += m + 1 - arr[i]
				arr[i] = m + 1
			m = arr[i]
		return res


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		val = arr[0]
		ans = 0
		for x in arr:
			if x > val:
				val = x + 1
			else:
				ans += val - x
				val += 1
		return ans


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		count = 0
		for index in range(1, N):
			if arr[index] <= arr[index - 1]:
				val = arr[index - 1] - arr[index] + 1
				count += val
				arr[index] += val
		return count


class Solution:

	def minIncrements(self, arr, N):
		if N == 1:
			return 0
		arr.sort()
		ans = 0
		max_val = 0
		for i in range(N):
			if arr[i] > max_val:
				max_val = arr[i]
			else:
				max_val += 1
				ans += max_val - arr[i]
		return ans


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		i = 1
		minop = 0
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				minop += arr[i - 1] - arr[i] + 1
				arr[i] = arr[i - 1] + 1
		return minop


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		ans = 0
		new = [arr[0]]
		for i in arr[1:]:
			if i > new[-1]:
				new.append(i)
			else:
				ans += new[-1] + 1 - i
				new.append(new[-1] + 1)
		return ans


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		inc = 0
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				temp = arr[i]
				arr[i] = arr[i - 1] + 1
				inc += arr[i] - temp
		return inc


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		s = set()
		ans = 0
		ma = 0
		for i in arr:
			ma = max(ma, i)
			if i not in s:
				s.add(i)
			else:
				ans += ma - i + 1
				s.add(ma + 1)
				ma = ma + 1
		return ans


class Solution:

	def minIncrements(self, a, n):
		a.sort()
		m = 0
		ans = 0
		for i in range(n):
			if m < a[i]:
				m = a[i]
			else:
				m = m + 1
				ans += m - a[i]
		return ans


class Solution:

	def minIncrements(self, arr, N):
		ans = 0
		arr = sorted(arr)
		for i in range(1, N):
			if arr[i - 1] >= arr[i]:
				ans += arr[i - 1] - arr[i] + 1
				arr[i] = arr[i - 1] + 1
		return ans


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		count = 0
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				v = arr[i - 1] - arr[i] + 1
				count += v
				arr[i] += v
		return count


class Solution:

	def minIncrements(self, arr, N):
		map = {}
		c = 0
		for i in arr:
			if i not in map:
				map[i] = 1
			else:
				k = i + 1
				while True:
					c += 1
					if k not in map:
						map[k] = 1
						break
					else:
						k += 1
		return c


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		x1 = sum(arr)
		for i in range(1, N):
			if arr[i - 1] == arr[i]:
				arr[i] += 1
			elif arr[i - 1] > arr[i]:
				arr[i] = arr[i - 1] + 1
		x2 = sum(arr)
		return x2 - x1


class Solution:

	def minIncrements(self, arr, N):
		minIncre = 0
		i = 0
		sets = {'o'}
		while i < N:
			if arr[i] in sets:
				arr[i] += 1
				minIncre += 1
				continue
			sets.add(arr[i])
			i += 1
		return minIncre


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		sum = 0
		max = arr[0]
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				sum += max + 1 - arr[i]
				arr[i] = max + 1
			max = arr[i]
		return sum


class Solution:

	def minIncrements(self, arr, n):
		arr.sort()
		ans = 0
		for i in range(1, n):
			if arr[i] <= arr[i - 1]:
				want = arr[i - 1] + 1
				have = arr[i]
				ans += want - have
				arr[i] = want
		return ans


class Solution:

	def minIncrements(self, a, n):
		a.sort()
		res = 0
		for i in range(1, n):
			if a[i - 1] >= a[i]:
				res += a[i - 1] - a[i] + 1
				a[i] += a[i - 1] - a[i] + 1
		return res


class Solution:

	def minIncrements(self, arr, N):
		arr = sorted(arr)
		count = 0
		l = 0
		r = 1
		while r != N:
			if arr[l] >= arr[r]:
				arr[r] += 1
				count += 1
			else:
				l += 1
				r += 1
		return count


class Solution:

	def minIncrements(self, arr, n):
		increment = 0
		arr.sort()
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				while arr[i] <= arr[i - 1]:
					increment += 1
					arr[i] += 1
		return increment


from collections import Counter

class Solution:

	def minIncrements(self, arr, N):
		a = Counter(arr)
		ans = 0
		for i in set(arr):
			if a[i] > 1:
				flag = i
				for t in range(a[i] - 1):
					while flag in a:
						flag += 1
					ans += flag - i
					a[flag] = 1
		return ans


class Solution:

	def minIncrements(self, arr, N):
		c = 0
		y = sum(arr)
		arr.sort()
		for i in range(1, N):
			if arr[i] < arr[i - 1]:
				arr[i] += arr[i - 1] - arr[i]
				h = arr[i - 1] - arr[i]
				c += h
			if arr[i] == arr[i - 1]:
				arr[i] += 1
				c += 1
		return sum(arr) - y


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		total = 0
		start = 0
		i = 1
		while i < N:
			if arr[i] == arr[i - 1]:
				total += 1
				arr[i] += 1
			elif arr[i] < arr[i - 1]:
				diff = arr[i - 1] - arr[i]
				total += diff + 1
				arr[i] = arr[i - 1] + 1
			i += 1
		return total


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		co = 0
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				val = arr[i - 1] - arr[i] + 1
				co += val
				arr[i] += val
		return co


class Solution:

	def minIncrements(self, arr, N):
		s = set()
		inc = 0
		for i in arr:
			while i in s:
				inc = inc + 1
				i = i + 1
			s.add(i)
		return inc


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		ans = 0
		for i in range(1, len(arr)):
			pre = arr[i - 1]
			cur = arr[i]
			if pre >= cur:
				ans += pre - cur + 1
				arr[i] = pre + 1
		return ans


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		i = 0
		j = 1
		l = -1
		r = -1
		out = 0
		while i < N:
			if i == N - 1:
				l = arr[i] + 1
				r = 1000000000
			elif arr[i] + 1 < arr[i + 1]:
				l = arr[i] + 1
				r = arr[i + 1] - 1
			if l != -1:
				while j < N:
					if arr[j - 1] == arr[j]:
						if l <= arr[j] and arr[j] < r:
							l = arr[j] + 1
						elif l < arr[j] and r <= arr[j]:
							l = -1
							r = -1
							break
						out += l - arr[j]
						l += 1
						if l > r:
							l = -1
							r = -1
							j += 1
							break
					j += 1
			i += 1
		return out


class Solution:

	def minIncrements(self, arr, N):
		n = N
		arr.sort()
		ans = 0
		for i in range(1, n):
			if arr[i] <= arr[i - 1]:
				d = arr[i - 1] - arr[i]
				ans += d + 1
				arr[i] += d + 1
		return ans


class Solution:

	def minIncrements(self, arr, N):
		lmap = {}
		cnt = 0
		for i in arr:
			if i not in lmap:
				lmap[i] = 1
			else:
				k = i + 1
				while True:
					cnt += 1
					if k not in lmap:
						lmap[k] = 1
						break
					else:
						k += 1
		return cnt


class Solution:

	def minIncrements(self, arr, N):
		c = 0
		arr.sort()
		for h in range(1, N):
			if arr[h] <= arr[h - 1]:
				while arr[h - 1] >= arr[h]:
					arr[h] += 1
					c += 1
		return c


class Solution:

	def minIncrements(self, arr, N):
		d = {}
		arr.sort()
		count = 0
		for i in range(N):
			if arr[i] not in d:
				d[arr[i]] = 1
				maxi = arr[i]
			else:
				k = maxi + 1 - arr[i]
				count += k
				maxi = arr[i] + k
				d[maxi] = 1
		return count


import collections

class Solution:

	def minIncrements(self, nums, N):
		nums.sort()
		max_val = nums[-1]
		nums.append(len(nums) + max_val)
		moves = taken = 0
		for i in range(1, len(nums)):
			if nums[i - 1] == nums[i]:
				taken += 1
				moves -= nums[i]
			else:
				give = min(taken, nums[i] - nums[i - 1] - 1)
				moves += give * (give + 1) // 2 + give * nums[i - 1]
				taken -= give
		return moves


class Solution:

	def minIncrements(self, arr, N):
		ans = 0
		uni_arr = set()
		for i in arr:
			while i in uni_arr:
				i += 1
				ans += 1
			uni_arr.add(i)
		return ans


class Solution:

	def minIncrements(self, arr, n):
		arr.sort()
		count = sum(arr)
		for i in range(1, n):
			if arr[i] <= arr[i - 1]:
				arr[i] = arr[i - 1] + 1
		return sum(arr) - count


class Solution:

	def minIncrements(self, arr, n):
		arr.sort()
		s = set()
		count = 0
		for i in range(1, n):
			while arr[i] <= arr[i - 1]:
				arr[i] += 1
				count += 1
		return count


class Solution:

	def minIncrements(self, arr, N):
		arr = sorted(arr)
		sum1 = 0
		max1 = 0
		dic = {}
		for i in range(len(arr)):
			if arr[i] not in dic:
				dic[arr[i]] = True
				max1 = max(max1, arr[i])
			else:
				sum1 += max1 + 1 - arr[i]
				max1 += 1
				dic[max1] = True
		return sum1


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		ops = 0
		last = -1
		for i in arr:
			if i <= last:
				ops += last - i + 1
				last += 1
			else:
				last = i
		return ops


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		di = {}
		(nm, su) = (0, 0)
		for i in arr:
			nm = max(i, nm)
			if i in di:
				su += nm + 1 - i
				nm += 1
				di[nm] = 1
			else:
				di[i] = 1
		return su


class Solution:

	def minIncrements(self, arr, N):
		count = 0
		arr_copy = set()
		for i in range(N):
			t = arr[i]
			while t in arr_copy:
				count += 1
				t += 1
			arr_copy.add(t)
		return count


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		ops = 0
		for i in range(1, len(arr)):
			if arr[i] == arr[i - 1]:
				cur_val = arr[i]
				j = i
				while j < len(arr) and arr[j] == cur_val:
					arr[j] += 1
					ops += 1
					j += 1
		return ops


class Solution:

	def minIncrements(self, arr, N):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		c = 0
		for i in arr:
			if d[i] != 1:
				d[i] -= 1
				a = i
				while a in d:
					a += 1
					c += 1
				d[a] = 1
		return c


class Solution:

	def minIncrements(self, arr, n):
		arr.sort()
		count = 0
		for i in range(1, n):
			if arr[i] <= arr[i - 1]:
				val = arr[i - 1] - arr[i] + 1
				count += val
				arr[i] += val
		return count


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		i = 0
		count = 0
		temp = set()
		while i < N:
			ele = arr[i]
			if ele in temp:
				arr[i] = ele + 1
				count += 1
			else:
				temp.add(ele)
				i += 1
		return count


import heapq

class Solution:

	def minIncrements(self, arr, N):
		set1 = set()
		arr.sort()
		ans = 0
		max1 = 0
		for i in range(len(arr)):
			max1 = max(max1, arr[i])
			if arr[i] in set1:
				ans += max1 + 1 - arr[i]
				max1 = max1 + 1
				set1.add(max1)
			else:
				set1.add(arr[i])
		return ans


from statistics import *

class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		count = 0
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				want = arr[i - 1] + 1
				have = arr[i]
				diff = want - have
				count = count + diff
				arr[i] = want
		return count


class Solution:

	def minIncrements(self, arr, N):
		arr.sort()
		opr = 0
		i = 1
		while i < N:
			if arr[i - 1] >= arr[i]:
				temp = arr[i - 1] - arr[i] + 1
				opr += temp
				arr[i] = arr[i - 1] + 1
			i += 1
		return opr