C - Gap Existence Editorial by en_translator
For a fixed \(j\), the value \(A_i\) such that \(A_i-A_j=X\) is unique, so it is sufficient to determine if \(A\) has such a value.
Naively scanning the array costs at worst an \(\Omega(N)\) time each, for a total of \(\Omega (N^2)\) time, exceeding the execution time limit. Same applies if you use find
for a vector
in C++, in
for a list
in Python, and contains
for a list in Java. Beware of the complexities of the standard libraries, too.
If you maintain \(A\) in a set
, it costs an \(O(\log N)\) time each, for a total of \(O(N\log N)\) time, fitting in the time limit.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,x;
cin >> n >> x;
set<int>s;
for(int i=0;i<n;i++){
int t;
cin >> t;
s.insert(t);
}
for(auto a:s){
if(s.find(a+x)!=s.end()){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
}
You can also use the sliding window trick to solve it in a linear time except for sorting.
We sort \(A\) in ascending order, as it does not affect the answer.
When searching for \(i\) for a fixed \(j\), if you iterate \(j\) in ascending order, the corresponding \(i\) also increases monotonically, so you can scan all \(j\) in a linear time.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,x;
cin >> n >> x;
vector<int>a(n);
for(int i=0;i<n;i++)cin >> a[i];
sort(a.begin(),a.end());
int i=0;
for(int j=0;j<n;j++){
while(i<n&&a[i]-a[j]<x)i++;
if(i<n&&a[i]-a[j]==x){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
}
posted:
last update: