In this HackerEarth New game of Oz problem solution, 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 selects a random number from arr[]. Say the 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 take turns until arr[] becomes empty. Oz loves this game so he wants to make a maximum number of possible turns. Help Oz to make a maximum number of possible turns.


HackerEarth New game of Oz problem solution

HackerEarth New game of Oz problem solution.

#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<bitset>
#include<assert.h>
#include<algorithm>
#include<vector>
#include<set>
#include<limits.h>
#include<map>
#include<stack>
#include<stdio.h>
#include<queue>
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007 // 10**9 + 7
#define INF 1e9
#define FOR(i,a,b) for(int (i) = (a); (i) < (b); ++(i))
#define RFOR(i,a,b) for(int (i) = (a)-1; (i) >= (b); --(i))
#define CLEAR(a) memset((a),0,sizeof(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, b, a) for (int i = b; i > a; i--)
#define all(v) v.begin(), v.end()
#define GETCHAR getchar_unlocked
#define pi(n) printf("%d\n",n)
#define pll(n) printf("%lld\n",n)
#define rk() int t; scanf("%d",&t); while(t--)
using namespace std;
const double pi = acos(-1.0);
//freopen("in","r",stdin);
//freopen("out","w",stdout);

const int er[8] = {-1,-1,0,1,1,1,0,-1};
const int ec[8] = {0,1,1,1,0,-1,-1,-1};
const int fr[4] = {-1,1,0,0};
const int fc[4] = {0,0,1,-1};
typedef unsigned long long ull;
typedef long long ll;
typedef long l;
typedef pair<int,int> pii;
typedef vector<int> vec;
typedef vector<pii> vpii;
ll po(ll a,ll p)
{ll ret = 1;while(p){if(p&1)ret = (ret*a)%mod;a=(a*a)%mod;p=p>>1;}return ret%mod;}

int getans(vector<int> &res){
  int ans = 0;                                
  sort(res.begin(), res.end());
  int size = 0;                           
  for(int i = 0; i < res.size(); i++){
    int ff = 0;                                                             
    if(i == 0 || res[i] == res[i-1] + 1)size++;
    else {
      ff = size;                           
      size = 1;
    }
    ans += (ff+1)/2;
    if(i == res.size()-1)ans += (size+1)/2;                     
  }
  return ans;
}

int main(){
  rk(){
    int n;
    cin>>n;
    vector<int>v;
    for(int i=0;i<n;i++){
      int a;
      cin>>a;
      v.pb(a);
    }
    int ans=getans(v);
    cout<<ans<<endl;
  }
}


Second solution

#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n) 
{LL ret=1;LL b=a;while(n) {if(n&1) 
    ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
int main()
{
    int t;
    sd(t);
    assn(t,1,100);
    while(t--){
        int n,ar[109],ans=0;
        sd(n);
        assn(n,1,100);
        for(int i=0; i<n; i++)
            sd(ar[i]),assn(ar[i],1,1000);
        sort(ar,ar+n);
        for(int i=0; i<n; i++){
            ans++;
            if(i!=n-1 and ar[i+1]==ar[i]+1)i++;
        }
        cout << ans << endl;
    }
    return 0;
}