C++|Engaging Explanation and comments | SIEVE kind of logic | image | O(nlog(log(max))) | plz Upvote
\n\nWhen we first encounter this question it seems like we need to do it for all pairs \nthat is Nc2 PAIRS or n(n-1)/2  which will give TLE\n\n1. For each a[i] 
![image](https://assets.leetcode.com/users/images/2bad3ec3-cf03-4fa7-9a46-8bf68917673d_1621228992.583361.jpeg)\n\nWhen we first encounter this question it seems like we need to do it for all pairs \nthat is Nc2 PAIRS or n*(n-1)/2  which will give TLE\n\n1. For each a[i]  we need to consider only numbers greater than a[i] , (This is where SIEVE comes into picture)\n\n2.  For eg a=[2,2,2,2,3,3,3,3,4,4,4,5,5,5,7,7,8,8,9,9]\n      \n\t  For a[i]=2 we need to consider intervals like [2,3], [4,5], [6,7], [8,9]  and so on \n\t  For a[i]=3 we need to consider intervals like [3,5],  [6,8], [9,11]  and so on\n\t  For a[i]=4 we need to consider intervals like [4,7] , [8,11]  and so on\n\t  \n\t  So generalising for all into interavals in format [start,end] (CRUX of SIEVE)\n\t  For a[i]=x we need to consider [x, 2*x-1] , [2*x, 3*x-1] , [3*x, 4*x-1]     and so on\n\t  \n3.  for each interval  [start,end] we need to consider no of elements in [start,end] and its floor value like \n       for eg a[i] =x \n\t   1.  for interval containing elements v= [x, 2*x-1] we get floor_val = v[j]/a[x] (0<=j<=v.size) **( which is same for all elements of v[] )**\n\t\t \n\t\t \n\t\t2.  and frequency of no of elements between x to 2*x-1 we make a prefix array \n\t\t     where pref [i] = no of elements smaller than i\n\t\t    we get frequency = pref[2*x-1]-pref[x-1]\n\t\t\t or       frequency = pref[end]-pref[start-1]\n  \n  4. So we need to do step 3 for all a[i]\n\n   **Corner case**\n  5. Each time u have to select a window of  [start , end] **the last window will not come completely so we change our end pointer like  refer the picture**\n    **end=min(mx,start+num-1); **  \n  \n  \n                                                                                                                                                                                                                                   \n**plz Upvote if it helps**\n\n```\nclass Solution {\npublic:\n    \n    int mod=1e9+7;\n    \n    int add(int a,int b){\n        \n        return (mod + (a%mod) + (b%mod))%mod;\n    }\n    \n    int sumOfFlooredPairs(vector<int>& a) {\n        \n       \n        int ans=0,i,n=a.size(),mx=-1,num,start,end;\n        \n        const int N=1e5+1;\n        int pref[N]={0};\n        \n        // store frequency of each number\n        for(i=0;i<n;i++){\n            pref[a[i]]++;\n            mx=max(mx,a[i]);\n        }\n        \n        \n        // make prefix array storing frequency of all numbers<=nums in pref[num]\n        for(i=1;i<=100000;i++){\n            pref[i]=add(pref[i],pref[i-1]); //pref[num]=pref[num]+pref[num-1]; \n                                            \n        }\n        \n     \n        \n        // For each num check how many valid-pairs(non-zero value of floor) we can get ie numbers>=num will make a valid pair ie floor(number/num)>=1\n        for(i=0;i<n;i++){  \n            \n            num=a[i];\n          \n            for(start=num; start<=mx; start=start+num){ // now check for ranges of numbers [start,end] such that it is like [x,2*x-1], \n                                                          // [2*x, 3*x-1], \n                \n                end=min(mx,start+num-1);   //  for last window we have to consider partial part only refer picture \n                \n                \n                int floor_val=start/num;\n                \n                int fre=(pref[end]-pref[start-1] + mod)%mod;\n                \n                int contri=((floor_val%mod)*(fre%mod))%mod;\n                \n             \n                \n                ans=add(ans,contri);\n            }\n            \n           \n        }\n        \n        \n        \n        \n        return ans;\n        \n        \n    }\n};\n\n\n/*\ntestcase\n[2,2,2,3,3,3,3,5,6,7,7,7,7,7,7,7,1,3]\n*/\n```
[]