Given an array of distinct positive numbers, the task is to calculate the minimum number of subsets (or subsequences) from the array such that each subset contains consecutive numbers.
 
Example 1:
Input:
N = 10
Arr[] = {100, 56, 5, 6, 102, 58, 101, 57, 7, 103} 
Output:
3
Explanation:
{5, 6, 7}, { 56, 57, 58}, {100, 101, 102, 103} are
3 subset in which numbers are consecutive.
 
Example 2:
Input:
N = 3
Arr[] = {10, 100, 105}
Output:
3
Explanation:
{10}, {100} and {105} are 3 subset
in which numbers are consecutive.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function numofsubset() which takes the array Arr[] and its size N as inputs and returns the count of number of such subset's that contains consecutive numbers.
 
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N≤ 10^{5}
1 ≤ A[] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def numofsubset(self, arr, n):
        # Your code goes here

Solutions:
class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		subsets = 1
		i = 0
		while i < n - 1:
			if arr[i + 1] != arr[i] + 1:
				subsets += 1
			i += 1
		return subsets


class Solution:

	def numofsubset(self, arr, n):
		x = sorted(arr)
		count = 1
		for i in range(0, n - 1):
			if x[i] + 1 != x[i + 1]:
				count += 1
		return count


class Solution:

	def numofsubset(self, arr, n):
		k = {}
		ans = 0
		for i in arr:
			k[i] = 1
		for i in arr:
			if i - 1 in k:
				continue
			else:
				ans += 1
		return ans


class Solution:

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


class Solution:

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


class Solution:

	def numofsubset(self, arr, n):
		lists = []
		l = []
		arr.sort()
		i = 0
		while i < len(arr):
			if i == 0:
				l.append(arr[i])
				i += 1
				continue
			if arr[i] - arr[i - 1] == 1:
				l.append(arr[i])
			else:
				lists.append(l)
				l = []
				l.append(arr[i])
			i += 1
		if len(l) > 0:
			lists.append(l)
		return len(lists)


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		c = 1
		for i in range(len(arr) - 1):
			if arr[i] + 1 == arr[i + 1]:
				continue
			else:
				c += 1
		return c


class Solution:

	def numofsubset(self, arr, n):
		i = 1
		count = 1
		arr = sorted(arr)
		while i < len(arr):
			if arr[i] == arr[i - 1] + 1:
				i += 1
			else:
				count += 1
				i += 1
		return count


class Solution:

	def numofsubset(self, arr, n):
		arr = sorted(arr)
		cnt = 1
		i = 1
		while i < n:
			if arr[i] == arr[i - 1] + 1:
				while i < n and arr[i] == arr[i - 1] + 1:
					i += 1
				if i != n:
					cnt += 1
			else:
				cnt += 1
			i += 1
		return cnt


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		count = 0
		j = 0
		while j < n - 1:
			if arr[j + 1] - arr[j] == 1:
				j = j + 1
			else:
				count = count + 1
				j = j + 1
		return count + 1


class Solution:

	def numofsubset(self, arr, n):
		i = 1
		c = 1
		arr.sort()
		while i < n:
			if arr[i] - 1 == arr[i - 1]:
				i += 1
			else:
				c += 1
				i += 1
		return c


class Solution:

	def numofsubset(self, arr, n):
		shreya = 0
		arr = sorted(arr)
		for i in range(1, n):
			if abs(arr[i] - arr[i - 1]) != 1:
				shreya = shreya + 1
		return shreya + 1


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		s = 0
		for i in range(1, n):
			if abs(arr[i] - arr[i - 1]) != 1:
				s = s + 1
		return s + 1


class Solution:

	def numofsubset(self, nums, n):
		if len(nums) == 0:
			return 0
		nums.sort()
		ans = 0
		curr_count = 0
		last_smaller = float('-inf')
		for i in range(len(nums)):
			if nums[i] - 1 == last_smaller:
				curr_count += 1
				last_smaller = nums[i]
			elif nums[i] != last_smaller:
				curr_count = 1
				ans += 1
				last_smaller = nums[i]
		return ans


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		cou = 0
		for i in range(n - 1):
			if arr[i] + 1 == arr[i + 1]:
				continue
			else:
				cou += 1
		return cou + 1


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		c = 1
		for i in range(n - 1):
			if arr[i] + 1 != arr[i + 1]:
				c += 1
		return c


class Solution:

	def numofsubset(self, arr, n):
		if n == 1:
			return 1
		arr.sort()
		j = 0
		res = []
		for i in range(1, n):
			if arr[i - 1] + 1 != arr[i]:
				res.append(arr[j:i])
				j = i
			if i == n - 1:
				res.append(arr[j:])
		return len(res)


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		(L, K) = ([], [])
		k = 0
		for i in range(n - 1):
			if arr[i + 1] == arr[i] + 1:
				L.append(arr[i])
				k += 1
			else:
				L.append(arr[i])
				k += 1
				K.append(L)
				L = []
		return len(K) + n - k


class Solution:

	def numofsubset(self, arr, n):
		arr = sorted(arr)
		count = 0
		for i in range(n - 1):
			if arr[i] + 1 != arr[i + 1]:
				count += 1
		count += 1
		return count

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.numofsubset(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def numofsubset(self, l, n):
		st = set(l)
		ans = 0
		for i in range(n):
			if l[i] - 1 not in st:
				ans += 1
		return ans


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		cnt = 0
		res = 1
		for i in range(1, n):
			if arr[i] - arr[i - 1] == 1:
				cnt += 1
			else:
				res += 1
				cnt = 0
		return res


class Solution:

	def numofsubset(self, arr, n):
		seti = set(arr)
		new = set()
		total = 0
		for i in arr:
			if i - 1 not in seti:
				new.add(i)
				total += 1
			else:
				seti.remove(i - 1)
		return total


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		cnt = 1
		for i in range(len(arr) - 1):
			if arr[i] + 1 != arr[i + 1]:
				cnt += 1
		return cnt


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		count = 1
		for x in range(len(arr) - 1):
			if arr[x] != arr[x + 1] - 1:
				count += 1
		return count


class Solution:

	def numofsubset(self, arr, n):
		if len(arr) == 0:
			return 0
		if len(arr) == 1:
			return 1
		arr = sorted(arr, reverse=False)
		Count = 1
		i = 0
		j = 0
		while j < len(arr) - 1:
			if arr[j + 1] - arr[j] == 1:
				j += 1
			else:
				j += 1
				i = j
				Count += 1
		return Count


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		count = 0
		for i in range(len(arr)):
			if i == 0:
				count += 1
			elif arr[i - 1] == arr[i] - 1:
				pass
			else:
				count += 1
		return count


class Solution:

	def numofsubset(self, arr, n):
		arr.sort()
		res = []
		temp = []
		for i in arr:
			if len(temp) == 0:
				temp.append(i)
			if i - temp[-1] == 1:
				temp.append(i)
			else:
				res.append(temp)
				temp = [i]
		return len(res)