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();  
}