new-game-of-oz

Today Oz is playing a new game. He has an array arr[] of N distinct integers . In each turn he is will follow two actions - 
1) He select a random number from arr[]. Say value of this element is X.
2) He will remove X from arr[]. if X-1 is present in arr[] then he will remove it. if X+1 is present in arr[] then he will remove it.
Oz will make turns until arr[] becomes empty. Oz loves this game so he wants to make maximum number of possible turns. Help Oz to make maximum number of possible turns. 

Input :
The first line contains the number of test cases - T . Each test case consist of two lines. First line will contain a integer N - number of elements in arr[]. Second line will contain N space separated integers.

Output :
For each test case output maximum number of possible turns that Oz can make.

Constraints :
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ each element of arr[]  ≤ 1000

SAMPLE INPUT
1
6
291 292 295 297 298 299

SAMPLE OUTPUT
4

Explanation

One of the possible way to make 4 turns is by choosing the following elements in each turn: 297, 299, 295, 292.

Source: hackerearth | Difficulty: EASY
Tags: Sorting

Ad-hoc


Solutions:
import sys
import math

# def cal_move(n):
# 	return int(math.ceil(2*n/3))
	

# t=int(raw_input().strip())
# for i in range(0,t):
# 	n=int(raw_input().strip())
# 	arr=map(int,raw_input().strip().split(" "))
# 	arr.sort()
# 	moves=0
# 	c=1
# 	for j in range(0,n-1):
# 		if(abs(arr[j]-arr[j+1])==1):
# 			c=c+1
# 			continue
# 		else:
# 			if c>=2:
# 				moves=moves+cal_move(c)
# 				c=1
# 			else:
# 				moves=moves+1
# 	if c>=2:
# 		moves=moves+cal_move(c)
# 	else:
# 		moves=moves+1
# 	print int(moves)
for _ in range(eval(input())):
	n=eval(input())
	arr=list(map(int,input().split()))
	arr=sorted(arr)
	#print arr
	i=0
	count=0
	l=len(arr)
	art=[0]*l
	while i<l:
		x=arr[i]
		count+=1
		#print i,x,count
		if i+1<l:
			if arr[i+1]==arr[i]+1:
				arr[i+1]=0
				i=i+1
		i=i+1
	print(count)
	


import sys
t = int(eval(input()))
while t >0:
	t-=1
	n=int(eval(input()))
	s=input().split()
	s=list(map(int,s))
	s.sort(reverse=True)
	count=0
	for i in s:
		count+=1
		if i-1 in s:
			s.remove(i-1)
	print(count)
		


import sys
import math
test=int(eval(input()))

for i in range(test):
	n=int(eval(input()))
	
	arr=[0]*n
	arr=list(map(int,sys.stdin.readline().split()))
	arr.sort()
	answer=0
	j1=n-1
	if(j1==0):
		j1=j1-1
	while(j1!=-1):
		if(arr[j1-1]==(arr[j1]-1)):
			j1=j1-2
		else:
			j1=j1-1
		answer=answer+1
		if(j1==0):
			answer=answer+1
			j1=j1-1
	if(n==1):
		answer=answer+1
	
	print(answer)        
	


for tc in range(eval(input())):
	n=eval(input())
	no=[0 for i in range(1002)]
	for i in input().split():
		no[int(i)]=1
	count=0
	i=1
	while i < 1001:
			count+=no[i]
			i+=(no[i] and no[i+1])+1
	print(count)
	
	


def main():
	t=int(input())
	while t!=0:
		n=int(input())
		arr=input()
		arr=arr.split(" ")
		arr=sorted(arr,key=int)
		count=0
		while len(arr)!=0:
			a=arr.pop(0)
			count+=1
			if len(arr)==0:
				break
			if int(arr[0])==(int(a)+1):
				arr.pop(0)
		print(count)
		t=t-1

if __name__=='__main__':
	main()
		
			


def calc (list_):
	count = 0
	while True:
		if list_ == []:
			return count
		count +=1
		tlist_ = list_
		found = False
		for elem in tlist_:
			if elem+1 not in tlist_ and elem-1 not in tlist_:
				list_.remove (elem)
				found=True
				break

		if found == True: continue

		for elem in tlist_:
			if elem+1 not in tlist_:
				list_.remove (elem)
				list_.remove (elem-1)
				found=True
				break

		if found == True: continue

		for elem in tlist_:
			if elem+1 not in tlist_:
				list_.remove (elem)
				list_.remove (elem+1)
				found=True
				break

		list_.pop(0)
		if list_ !=[]:
			list_.pop(1)


def _get_list (str_):
	li = []
	for numstr in str_.split():
		li.append ( int (numstr.strip()))
   
	return li

for i in range (0, int(input())):
	l=input()
	print(calc (_get_list (input())))


from collections import *
from heapq import *
from bisect import *
from math import *
from itertools import *
inf=float('inf')


if __name__=="__main__":
	tcase=int(input())
	while tcase>0:
		tcase-=1
		n = int(input())
		arr = list(map(int,input().split()))
		arr.sort()
		turns = 0
		i = 0
		while i<n:
			if i+1 == n:
				turns+=1
				break
			if arr[i]+1 == arr[i+1]:
				i+=2
				turns +=1
			else:
				turns+=1
				i+=1
		print(turns)

# 291 292 295 297 298 299


listIs = []
num_cases = int(input())

for numberOfCases in range(num_cases):
	
	count = 0
	flag = 0
	num_elements = int(input())
	
	

	

	get_input = input()
	listIs = get_input.split()
	#print 'list is'
	
	for index in range(len(listIs)):
		listIs[index] = int(listIs[index])

	'''print type(listIs)
	for elements in listIs:
		print type(elements)

	break'''
	listIs.sort()
	index = 0
	if (len(listIs) == 1):
		val = 1
		print(val)
	else :
		while (len(listIs) != 0):

			#print 'flag is ',flag
			if (flag == 0 and listIs[index+1] == listIs[index]+1):

				listIs.pop(index)
				listIs.pop(index)
				count = count + 1;
			#print 'here_if'
			else:
				listIs.pop(index)
				count = count + 1
				#print 'here_else'
			if (len(listIs)==1):
				flag = 1
		print(count)



from math import ceil

def getCnt(n):
	
	return int(round(float(n)/float(2)))
	
for t in range(eval(input())):
	L =eval(input())
	cnt = 0
	
	ar = sorted(map(int,input().split(' ')))
	
	#print 'ar', ar
	if not ar :
		continue
	elif L == 1:
		print(1)
		continue
	
	
	i = 1
	seq_len  = 1
	while i < L:
		#print i,ar[i-1],ar[i]
		if ar[i] == ar[i-1]+1: 
			seq_len += 1
		else :
			#print seq_len,'adding',getCnt(seq_len)
			cnt += getCnt(seq_len)
			seq_len = 1
			
		i+=1
	if i == L :
		#print 'seq_len',seq_len,getCnt(seq_len)
		cnt += getCnt(seq_len)
		
	print(cnt)


import sys
t = int(sys.stdin.readline().rstrip())
for i in range(t):
	n = int(sys.stdin.readline().rstrip())
	m = sys.stdin.readline().rstrip().split(" ")
	d = dict()
	for itm in m:
		d[int(itm)] = 1 + d.get(int(itm), 0)
	l = list(d.keys())
	c = 0
	while len(l) > 0:
		for itm in l:
			if itm - 1 not in d and itm + 1 not in d:
				c+=1
				l.remove(itm)
				del d[itm]

		for itm in l:
			if itm - 1 not in d and itm + 1 in d:
				c+=1
				l.remove(itm)
				del d[itm]
				l.remove(itm + 1)
				del d[itm + 1]

		for itm in l:
			if itm - 1 in d and itm + 1 not in d:
				c+=1
				l.remove(itm)
				del d[itm]
				l.remove(itm - 1)
				del d[itm - 1]

	print(c)


import sys
t = int(sys.stdin.readline().rstrip())
for i in range(t):
	n = int(sys.stdin.readline().rstrip())
	m = sys.stdin.readline().rstrip().split(" ")
	d = dict()
	for item in m:
		d[int(item)] = 1 + d.get(int(item), 0)
	l = list(d.keys())
	count = 0
	while len(l) > 0:
		for item in l:
			if item - 1 not in d and item + 1 not in d:
				count+=1
				l.remove(item)
				del d[item]
				#print "removing " + str(item)

		for item in l:
			if item - 1 not in d and item + 1 in d:
				count += 1
				l.remove(item)
				del d[item]
				l.remove(item + 1)
				del d[item + 1]
				#print "removing " + str(item) + str(item + 1)

		for item in l:
			if item - 1 in d and item + 1 not in d:
				count += 1
				l.remove(item)
				del d[item]
				l.remove(item - 1)
				del d[item - 1]
				#print "removing " + str(item) + str(item - 1)

	print(count)



t = eval(input())
for i in range(t):
	n = eval(input())
	a = list(map(int,input().split()))
	count = 0
	a.sort(reverse=True)
	# print "outside",a
	while a:
		
		count += 1
		j = a.pop()
		k = j + 1
		if k in a:
			a.pop()
		# print a
	print(count)


for tc in range(eval(input())):
	n=eval(input())
	no=[0 for i in range(1002)]
	for i in input().split():
		no[int(i)]=1
	count=0
	i=1
	while i < 1001:
			count+=no[i]
			i+=(no[i] and no[i+1])
			i+=1
	print(count)
	
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

cases = int(input())

for case in range(0,cases):
	
	ind = int(input())
	nos = list(map(int, input().split()))
	nos.sort()
	
	'''
	dif = [nos[i+1]-nos[i] for i in xrange(0,ind-1)]
	
	dif1 = filter(lambda x: x!=1, dif)
	print len(dif) - len(dif1) + 1
	'''
	dup = list(nos)
	
	c = ind-1
	for i in range(0,ind-1):
		if i < c:
			if nos[i+1] - nos[i] == 1:
				nos.remove(nos[i+1])
				c = c - 1
	print(len(nos))
		


from itertools import groupby
from operator import itemgetter
t=eval(input())
for dda in range(t):
	le=eval(input())
	akh=input()
	
	data = [int(s) for s in akh.split(' ')]
	data.sort()
	x=[]
	for k, g in groupby(enumerate(data), lambda i_x:i_x[0]-i_x[1]):
		x.append(list(map(itemgetter(1), g)))
	count=0
	for i in range(len(x)):
		if(len(x[i])==1):
			count=count+1
		else:
			rs=0
			rs=len(x[i])/2
			
			if(len(x[i])%2!=0):
				rs=rs+1
			count=count+rs
	print(count)


num_test=int(eval(input()))

while(num_test>0):
	num_elm=int(eval(input()))
	
	b=[int(i) for i in input().split()]
	
	b.sort()
	count=0
	j=num_elm-1
	
	while(j>-1):
		last=b[j]
		b.remove(last)
		count=count+1
		if(last-1 in b):
			b.remove(last-1)
			j=j-1
		
		
		if(j>0):
			first=b[0]
			b.remove(first)
			count=count+1
			if(first+1 in b):
				b.remove(first+1)
				
		j=len(b)-1
		
	num_test=num_test-1
	print(count)
	


	
	


t=int(input())
for i in range(t):
	n=int(input())
	#check=0
	ans=0
	arr=[]
	arr=(input().split())
	arr.sort(key=int)
	arr.append(0)
	j=0
	while j<n:
		#print j
		if((int(arr[j+1])-int(arr[j]))==1):
			#print "loop"
			ans=ans+1
			#print ans
			j=j+2
		else:
			j=j+1
			ans=ans+1
			#print ans
	#print "ans is"
	print(ans)


T = int(input())
for i in range (0,T):
	lenth = int(input())
	lenth = lenth - 1
	array_string  = input()
	array = array_string.split(" ")
	for j in range (lenth+1):
		array[j] = int(array[j])
	array.sort()
	j=0
	ans = 0
	lastaccess=0
	if lenth == 0:
		print("1")
		continue
	elif lenth == 1:
		if array[0]+1 == array[1]:
			print("1")
		else:
			print("2")
		continue
	while True:
		
		if j >= lenth-1:
			break
		if(array[j]+1 == array[j+1]):
			ans = ans + 1
			j = j + 2
			lastaccess = j-1
		else:
			ans = ans + 1
			j = j + 1
			lastaccess = j-1
	
	lastaccess = lastaccess + 1
	if lastaccess > lenth:
		print(ans)
	elif lastaccess == lenth:
		print(ans+1)
	else:
		if array[lastaccess]+1 == array[lastaccess+1]:
			print(ans+1)
		else:
			print(ans+2)


def ms_comb(strng, l, q, r):
	L = []
	R = []
	i = l
	while i <= q:
		L.append(int(strng[i]))
		i += 1
	while i <= r:
		R.append(int(strng[i]))
		i += 1
	L.append(1000000)
	R.append(1000000)
	i = 0
	j = 0
	k = l
	while k <= r:
		if(L[i] > R[j]):
			strng[k] = R[j]
			j += 1
		else:
			strng[k] = L[i]
			i += 1
		k += 1
	return strng


def ms(strng, l, r):
	if l < r:
		q = (l+r)/2
		ms(strng, l, q)
		ms(strng, q+1, r)
		return ms_comb(strng, l, q, r)
	else:
		strng[0] = int(strng[0])
		return strng


for i in range(eval(input())):
    n = eval(input())
    m = input().split()
    m = ms(m, 0, len(m)-1)
    turn = 0
    while(len(m) != 0):
	turn += 1
	n = m.pop(0)
	if len(m) == 0:
	    break
	if(n+1 == m[0]):
	    m.pop(0)
	
    print(turn)
	
	


# Read input from stdin and provide input before running code

t=int(input())
n=[]
l=[]
for i in range(t):
	n.append(int(input()))
	l.append(input())

for k in range(t):
	arr=list(map(int,l[k].split()))
	moves=0
	while len(arr)>0:
		count=[]
		for i in arr:
			if i+1 in arr and i-1 in arr:
				count.append(2)
			elif i+1 in arr or i-1 in arr:
				count.append(1)
			else:
				count.append(0)
		
		i= count.index(min(count))
		m = min(count)
		value =arr[i]
		if value+1 in arr:
			j=arr.index(value+1)
			count.pop(j)
			arr.pop(j)
		if value-1 in arr:
			j=arr.index(value-1)
			count.pop(j)
			arr.pop(j)
		count.remove(m)
		arr.remove(value)
		moves+=1
		del count
	print(moves)
	del arr


tc = eval(input())

while tc>0:
	n = eval(input())
	a = list(map (int, input().split()))
	a = sorted(a)
	# print a
	i = 0
	j = n-1
	c = 0

	while i<=j:
		c += 1
		if i<j:
			if a[i]+1==a[i+1] or a[i]-1==a[i+1]:
				# print "i: {} - {} {}".format(i, a[i], a[i+1])
				i += 1
		i += 1

		if i<=j:
			c+= 1
			if a[j-1]+1==a[j] or a[j-1]-1==a[j]:
				# print "j: {} - {} {}".format(j, a[j-1], a[j])
				j -= 1
		j -= 1        

	if n == 1:
		print(1)
	else :
		print(c) 

	tc -= 1



tc=int(input())
number_list=[]
while(tc>0):
	tc-=1
	n=input()
	number_list=list(map(int,input().split(" ")))
	number_list.sort()
	count=0
	while(len(number_list)>1):
		num=0;
		num=number_list[0]+1;
		if(num==number_list[1]):
			count+=1
			number_list.pop(0)
			number_list.pop(0)
		else:
			count+=1
			number_list.pop(0)
	if(len(number_list)==1):
		count+=1     
	print(count)
			
		
			
	


import sys
import math
t=int(eval(input()))
#t=1
for i in range(t):
	n=int(eval(input()))
	#n=6
	a=[0]*n
	a=list(map(int,sys.stdin.readline().split()))
	#a=[91,92,95,97,98,99]
	a.sort()
	#print a
	turn=0
	j=n-1
	if(j==0):
		j=j-1
	while(j!=-1):
	   # print j
		if(a[j-1]==(a[j]-1)):
			j=j-2
		else:
			j=j-1
		turn=turn+1
		if(j==0):
			turn=turn+1
			j=j-1
	if(n==1):
		turn=turn+1
	
	print(turn)        
	


t=int(input())
while(t):
	n=int(input())
	i=0
	counter=0
	list=list(map(int,input().split()))
	list.sort()
	while(i<n-1):
#		print i,list[i],list[i+1]
		if(list[i]+1==(list[i+1])):
#			print "te"
			i+=2
		else:
			i+=1
		counter+=1
	if(i==n-1):
		print(counter+1)
	else:
		print(counter)
	t-=1