Cool then Let me see
actually we can submit our solution after contest too.
How is answer 12?
Pairs:
1,2
1,3
2,3
3,5
Also i was thinking if sorting is done canβt we use two pointer approach.
First in the sorted array low will represent a starting position and high will represent the number which is just less than or equal to a[low]+k.
All numbers in range [low,high] will make a pair with low.
Each element is also count in subarray too as self-self = 0 <=K
Ok my bad I forgot to take screenshot of explaination -
Bro this is actually I did after sort take two pointers but in worst case it will be N2
Two pointer in sorted array will be O(N).
Okay, so answer.
My code earlier was for difference less than K and not including self.
int index = upper_bound(all(arr),a[i]+k) - arr.begin();
ans += index - i
Complete Code
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
signed main(){
int n,k;
cin >> n;
vector<int> a(n);
for(int &i: a)cin >> i;
cin >> k;
sort(a.begin(),a.end());
long long ans = 0;
for(int i = 0; i < n; ++i){
int index = upper_bound(a.begin(),a.end(),a[i]+k) - a.begin();
ans += index - i;
}
cout << ans;
return 0;
}
This is exactly u did what I thought but some bugs in implementation but in thought of partial marks I apply two pointers. Thanks once again .