Given an array Arr of N positive integers, find the missing elements (if any) in the range 0 to max of Arr_{i}. 
Example 1:
Input:
N = 5
Arr[] = {62, 8, 34, 5, 332}
Output: 0-4 6-7 9-33 35-61 63-331
Explanation: Elements in the range 0-4, 6-7, 
9-33, 35-61 and 63-331 are not present.
Example 2:
Input:
N = 4
Arr[] = {13, 0, 32, 500}
Output: 1-12 14-31 33-499
Explanation: Elements in the range 1-12, 
14-31 and 33-499 are not present.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMissing() which takes the array of integers arr and its size n as input parameters and returns a string denoting the missing elements. If
there are more than one missing, collate them using hyphen (-) and separate each different range with a space. If there are no missing element then return "-1".
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints
1 <= N <= 10^{7}
0 <= Arr_{i} <= 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def printMissing(self, arr, n):

        # code here

Solutions:
class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		s = ''
		l = 0
		cnt = 0
		for i in range(n):
			h = arr[i] - 1
			if h - l > 0:
				s += str(l) + '-' + str(h) + ' '
				cnt += 1
			if h - l == 0:
				s += str(l) + ' '
				cnt += 1
			l = arr[i] + 1
		if cnt == 0:
			s = '-1'
		return s


class Solution:

	def findMissing(self, arr, n):
		max1 = max(arr)
		count = 1
		str1 = ''
		low = -1
		high = 0
		arr1 = [False] * (max1 + 1)
		for i in range(n):
			arr1[arr[i]] = True
		for i in range(max1 + 1):
			if not arr1[i] and low == -1:
				low = i
			if arr1[i]:
				if len(str1) != 0:
					str1 += ' '
				if low > -1:
					high = i - 1
				if low == high:
					str1 += str(low)
				elif low > -1 and low < high:
					str1 += str(low) + '-' + str(high)
				low = -1
		if len(str1) > 0:
			return str1
		else:
			return -1


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		next = 0
		output = ''
		for item in arr:
			if item == next + 1:
				output += str(next) + ' '
				next = item + 1
			elif item > next + 1:
				output += str(next) + '-' + str(item - 1) + ' '
				next = item + 1
			elif item == next:
				next += 1
		return output if output else -1


class Solution:

	def findMissing(self, arr, n):
		a = ''
		arr.sort()
		a += '0-' + str(arr[0] - 1) + ' ' if arr[0] > 1 else ''
		a += '0' + ' ' if arr[0] == 1 else ''
		for index in range(n - 1):
			diff = arr[index + 1] - arr[index]
			if diff > 1 and arr[index] + 1 != arr[index] + diff - 1:
				a += str(arr[index] + 1) + '-' + str(arr[index] + diff - 1) + ' '
			elif diff > 1:
				a += str(arr[index] + 1) + ' '
		return a if a else -1


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		s = []
		if arr[0] > 1:
			s.append('0-' + str(arr[0] - 1) + '')
		elif arr[0] == 1:
			s.append('0')
		for i in range(n - 1):
			if arr[i + 1] - arr[i] <= 1:
				continue
			elif arr[i + 1] - arr[i] == 2:
				s.append(str(arr[i] + 1) + '')
			else:
				s.append(str(arr[i] + 1) + '-' + str(arr[i + 1] - 1) + '')
		s = '{0}'.format(', '.join(map(str, s)))
		s = s.replace(',', '')
		if len(s) == 0:
			return -1
		return s


class Solution:

	def findMissing(self, arr, n):
		maxi = max(arr)
		present = [False] * (maxi + 1)
		for i in arr:
			present[i] = True
		res = []
		i = 0
		while i <= maxi:
			if not present[i]:
				l = r = i
				while not present[i]:
					r = i
					i += 1
				res.append(str(l) + '-' + str(r)) if l != r else res.append(str(l))
			i += 1
		return ' '.join(res) if res else -1


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		prev = 0
		strs = ''
		for i in arr:
			if i - 1 - prev > 0:
				strs += ' ' + str(prev) + '-' + str(i - 1)
			if i - 1 - prev == 0:
				strs += ' ' + str(prev)
			prev = i + 1
		strs = strs.lstrip()
		if not strs:
			return -1
		return strs


class Solution:

	def findMissing(self, arr, n):
		m = max(arr)
		a = [-1] * (m + 1)
		for j in arr:
			a[j] = j
		s = 0
		e = 1
		k = 1
		r = []
		for j in range(m + 1):
			if a[j] == -1:
				e = j
				k = 0
			elif a[j] != -1 and k == 0:
				if s != e:
					r.append(str(s) + '-' + str(e))
				else:
					r.append(str(s))
				s = j + 1
				k = 1
			elif a[j] != -1 and k == 1:
				s = j + 1
		if len(r) == 0:
			return -1
		return ' '.join(r)


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		result = []
		lower = 0
		upper = arr[-1]
		if len(arr) == 0:
			self.outputToResult(lower, upper, result)
			return result
		if arr[0] > lower:
			self.outputToResult(lower, arr[0] - 1, result)
		for i in range(1, len(arr)):
			if arr[i] - arr[i - 1] > 1:
				self.outputToResult(arr[i - 1] + 1, arr[i] - 1, result)
		if upper > arr[-1]:
			self.outputToResult(arr[-1] + 1, upper, result)
		if len(result) == 0:
			return '-1'
		return ' '.join(result)

	def outputToResult(self, start, end, result):
		sb = ''
		if start == end:
			sb = str(start)
		else:
			sb = str(start) + '-' + str(end)
		result.append(sb)


class Solution:

	def findMissing(self, nums, n):
		lower = 0
		nums.sort()
		upper = max(nums)

		def formatrange(lower, upper):
			if lower == upper:
				return str(lower)
			return str(lower) + '-' + str(upper)
		result = []
		prev = lower - 1
		for i in range(len(nums) + 1):
			curr = nums[i] if i < len(nums) else upper + 1
			if prev + 1 <= curr - 1:
				result.append(formatrange(prev + 1, curr - 1))
			prev = curr
		if len(result) >= 1:
			return ' '.join(result)
		else:
			return -1


class Solution:

	def findMissing(self, arr, n):
		LIMIT = max(arr)
		str1 = ''
		seen = [False] * LIMIT
		for i in range(LIMIT):
			seen[i] = False
		for i in range(n):
			if arr[i] < LIMIT:
				seen[arr[i]] = True
		i = 0
		while i < LIMIT:
			if seen[i] == False:
				j = i + 1
				while j < LIMIT and seen[j] == False:
					j += 1
				p = j - 1
				if i + 1 == j:
					str1 += str(i) + ' '
				else:
					str1 += str(i) + '-' + str(p) + ' '
				i = j
			else:
				i += 1
		if str1 == '':
			str1 = '-1'
		return str1


class Solution:

	def findMissing(self, a, n):
		a.sort()
		missing = []
		if n == 1 and a[0] == 0:
			return -1
		if a[0] == 1:
			missing.append('0')
		elif a[0] != 0 and a[0] != 1:
			val = '0' + '-' + str(a[0] - 1)
			missing.append(val)
		for i in range(0, n - 1):
			if abs(a[i] - a[i + 1]) > 2:
				f = str(a[i] + 1)
				l = str(a[i + 1] - 1)
				final = f + '-' + l
				missing.append(final)
			elif abs(a[i] - a[i + 1]) == 2:
				missing.append(str(a[i] + 1))
		ans = ' '.join(missing)
		return ans


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		ans = ''
		lower = 0
		for element in arr:
			if element - lower > 1:
				ans = ans + str(lower) + '-' + str(element - 1) + ' '
			elif element - lower == 1:
				ans = ans + str(element - 1) + ' '
			lower = element + 1
		if not ans:
			return -1
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findMissing(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		t = ''
		if arr[0] != 0:
			f = arr[0] - 1
			if f == 0:
				t += '0 '
			else:
				t += '0-' + str(f) + ' '
		for i in range(n - 1):
			d = arr[i] + 1
			e = arr[i + 1] - 1
			if d == e:
				t += str(d) + ' '
			if d < e:
				t += str(d) + '-' + str(e) + ' '
		if len(t) == 0:
			return '-1'
		return t
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findMissing(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		ans = ''
		x = 0
		for i in arr:
			if i - x >= 1:
				if i - x == 1:
					ans += str(x) + ' '
				else:
					ans += str(x) + '-' + str(i - 1) + ' '
			x = i + 1
		if not ans:
			return -1
		return ans


class Solution:

	def findMissing(self, arr, n):
		s = ''
		arr.sort()
		if arr[0] != 0:
			if arr[0] == 1:
				s = s + '0' + ' '
			else:
				s = s + '0' + '-' + str(arr[0] - 1) + ' '
		for i in range(1, n):
			if arr[i] - arr[i - 1] == 2:
				s = s + str(arr[i] - 1) + ' '
			elif arr[i] - arr[i - 1] > 2:
				s = s + str(arr[i - 1] + 1) + '-' + str(arr[i] - 1) + ' '
		if len(s) == 0:
			return -1
		return s


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		l = []
		if arr[0] == 0:
			if n == 1:
				return -1
			else:
				rang = ''
		elif arr[0] == 1:
			rang = '0 '
		else:
			rang = '0-' + str(arr[0] - 1) + ' '
		for i in range(1, n):
			if arr[i] - arr[i - 1] > 2:
				rang += str(arr[i - 1] + 1) + '-' + str(arr[i] - 1) + ' '
			if arr[i] - arr[i - 1] == 2:
				rang += str(arr[i] - 1) + ' '
		return rang


class Solution:

	def findMissing(self, arr, n):
		x = ''
		arr.sort()
		if arr[0] == 0 and n == 1:
			return '-1'
		elif arr[0] == 1 and n == 1:
			return '0'
		if arr[0] != 0:
			k = arr[0] - 1
			if k > 0:
				x += '0' + '-' + str(k) + ' '
			else:
				x += '0' + ' '
		for i in range(n - 1):
			c = arr[i + 1] - arr[i]
			if c > 2:
				x += str(arr[i] + 1) + '-' + str(arr[i + 1] - 1) + ' '
			elif c == 2:
				x += str(arr[i] + 1) + ' '
		return x


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		ranges = []
		if len(arr) == 1:
			if arr[0] == 0:
				return '-1'
			elif arr[0] == 1:
				return '0'
			else:
				return '0-' + str(arr[0] - 1)
		elif arr[0] == 1:
			ranges.append((0, 0))
		elif arr[0] > 1:
			ranges.append((0, arr[0] - 1))
		rangeStart = 0
		rangeEnd = arr[0]
		for i in range(1, n):
			diff = arr[i] - arr[i - 1]
			if diff == 0 or diff == 1:
				pass
			elif diff == 2:
				v = arr[i] - 1
				ranges.append((v, v))
			elif diff > 2:
				ranges.append((arr[i - 1] + 1, arr[i] - 1))
		result = ''
		for el in ranges:
			if el[0] == el[1]:
				result = result + str(el[0]) + ' '
			else:
				result = result + str(el[0]) + '-' + str(el[1]) + ' '
		return result


class Solution:

	def findMissing(self, arr, n):
		lo = 0
		hi = max(arr)
		ans = []
		arr.sort()

		def add_range(a, b):
			diff = b - a
			if diff == 2:
				ans.append(str(a + 1))
			elif diff > 2:
				ans.append(str(a + 1) + '-' + str(b - 1))
		add_range(lo - 1, arr[0])
		for i in range(len(arr) - 1):
			add_range(arr[i], arr[i + 1])
		if not ans:
			return '-1'
		return ' '.join(ans)