Question
Given few elements and an integer K,find number of happy elements. Element X is happy if there exists at least 1 element whose absolute difference is less than K.
The complete question can be found here.
Solution by Nikhil Mohan.
Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void test()
{
ll n,k,l;
scanf("%lld",&n);
// to remove duplicate elements from array (we distinct elements only)
set<ll> s;
// to keep track of frequency of each element in given array
map<ll,int> m;
for(int i=0;i<n;i++)
{scanf("%lld",&l);
s.insert(l); //insertion in to set
m[l]++; // counting frequency for element l
}
//copying the set to array a(to acess previous,
//current and next element at a time)
// set by default sort the input , we dont need to sort the array
n=s.size();
ll a[n],i=0,count=0;
for(ll x : s) {a[i]=x;
i++; }
// loop to check (adjacent diff <=k )
//since we dont have previous element for a[0]
//we keep a separatle check for this (jst to avoid runtime error)
if(a[1]-a[0]<=k) count+=m[a[0]];
for(int i=1;i<n-1;i++)
{
// when this condition satisfies we increment the count by
//that element frequency.
if( a[i+1]-a[i]<=k || abs(a[i]-a[i-1])<=k) count+=m[a[i]];
}
//since we dont have next element for a[n-1] ,
//we keep a separatle check for this (jst to avoid runtime error)
if(a[n-1]-a[n-2]<=k) count+=m[a[n-1]];
// printing output
cout<<count;
}
//driver code
int main()
{
test();
}