MXRCI's blog

By MXRCI, history, 2 months ago, In English

Question link

My thought process : I thought like what we do in inversion count we add smaller numbers at index of fenwick and then count the sum from (sorted index+1 to n-1) , we can do same in this case like making array of (nums1[i] — nums2[i] — diff) and then finding the correct index (using binary search) at a particular i and then finding sum till that index to get count. but i guess i cant implement it correctly can u please help

Fenwicktree struct

struct fenwicktree{
    int n;
    vector<int> fn;
    
    void init(int _n){
        n = _n+1;
        fn.resize(n,0);
    } 
     
    void get(int x,int sum){
       for(x++;x<n;x+=(x&(-x))){
            fn[x] += sum;
        }
    }
    
    // sum from 1 to idx
    int _sum(int x){
        int ans = 0;
        for(x++;x>0;x-=(x&(-x))){
            ans += fn[x];
        }
        return ans;
    }
    
    int sum(int left , int right){
        return _sum(right) - _sum(left-1);
    }
};

Logic:


class Solution { public: long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) { int n = nums1.size(); fenwicktree tree; tree.init(n); vector<pair<int,int>> v; vector<int> a; for(int i = 0 ; i < n ; i++){ v.push_back({nums1[i]-nums2[i]-diff,i}); a.push_back({nums1[i]-nums2[i]-diff}); } sort(v.begin(),v.end()); sort(a.begin(),a.end()); int ans = 0; for(int i = 0 ; i < n ; i++){ int sum = v[i].first; int idx = v[i].second; int j = lower_bound(a.begin(),a.end(),sum+diff)-a.begin(); ans += tree._sum(j); tree.get(idx,1); } return ans; } };
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You don't need fenwick tree for this. Rearranging the equation given, you get:

(nums1[i] — nums2[i]) — (nums1[j] — nums2[j]) <= diff

Looking at the equation, you should realise that you only need one array "nums3" where nums3[i] = nums1[i] — nums2[i]. Now all you need to do is find number of pair (i, j) where nums3[i] — nums3[j] <= diff. So first, sort nums3 in ascending order. Then, for each element a in nums3, binary search the first element b such that a-b <= diff, or instead b >= a-diff. Notice, that every element after b will also work, so add (length of num3 — position of b) to some variable "ans". After you iterate through the entire list, you get your answer.