Official

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.

Sample code (C++)

#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.

Sample code (C++)

#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: