Skip to content
Programming101
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programmingoneonone

HackerEarth New game of Oz problem solution

YASH PAL, 31 July 2024
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("%dn",n)
#define pll(n) printf("%lldn",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("%dn",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;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes