In this HackerEarth Find the Next problem solution You are given an array A of length N. For any given integer X, you need to find an integer Z strictly greater than X such that Z is not present in the array A. You need to minimise the value of Z.


HackerEarth Find the Next! problem solution


HackerEarth Find the Next! problem solution.

#include <bits/stdc++.h>

#define ll long long
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin>>n>>q;
int
ll arr[n+1];
for(int i=0;i<n;i++) cin>>arr[i];
map<ll,ll> mp;
sort(arr,arr+n);
for(int i=0;i<n;){
int j=i;
for(;j<n-1;j++) if(arr[j]<arr[j+1]-1) break;
for(int k=i;k<=j;k++) mp[arr[k]]=arr[j];
i=j+1;
}
while(q--){
ll x;
cin>>x;
if(mp[x]==0){
if(mp[x+1]==0) cout<<x+1<<"\n";
else cout<<mp[x+1]+1<<"\n";
} else cout<<mp[x]+1<<"\n";
}
return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;

vector<int> Find_It (int Q, vector<int> &A, vector<int> &Queries, int N) {
sort(A.begin(),A.end());
map<int,int>ans;
ans[A[N-1]]=A[N-1]+1;
for(int i=N-2;i>=0;i--)
{
if(binary_search(A.begin(),A.end(),A[i]+1))
ans[A[i]]=ans[A[i+1]];
else ans[A[i]]=A[i]+1;
//cout<<ans[A[i]]<<" ";
}
//cout<<"\n";
vector<int>answer;int val;
for(int i=0;i<Q;i++)
{
int x=Queries[i];
int ind=lower_bound(A.begin(),A.end(),x)-A.begin();
//cout<<ind<<" ";//int val;
if(ind==N)
val=x+1,answer.push_back(x+1);
else if(A[ind]>x+1)
val=x+1,answer.push_back(x+1);
else
val=ans[A[ind]],answer.push_back(ans[A[ind]]);
//cout<<val<<"\n";
}
return answer;
// Write your code here

}

int main() {

ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
int Q;
cin >> Q;
vector<int> A(N);
for(int i_A=0; i_A<N; i_A++)
{
cin >> A[i_A];
}
vector<int> Queries(Q);
for(int i_Queries=0; i_Queries<Q; i_Queries++)
{
cin >> Queries[i_Queries];
}

vector<int> out_;
out_ = Find_It(Q, A, Queries, N);
for(int i_out_=0; i_out_<out_.size(); i_out_++)
{
cout <<out_[i_out_]<<endl;
}
return 0;
}