JAVA Readable Code
IDEA:\n Basic idea is for every number let say x . I am not going to check for [1,2,...x) . I know the answer of this range that is 0. Similarly for range [x,x+
**IDEA:**\n Basic idea is for every number let say x . I am not going to check for [1,2,...x) . I know the answer of this range that is 0. Similarly for range [x,x+1...2x) If we take floor of x with any value in this answer will be this. keeping this in mind have a eye on code and things will get clear to you .\n \n**CODE:**\n```\n public int sumOfFlooredPairs(int[] nums) {\n        int N=(int)1e5;\n        int mod=(int)1e9 + 7;\n        \n\t\t\n        int[] frequencyMap=new int[N+1];\n        for(int num:nums) frequencyMap[num]++;\n        \n        int[] prefixFreq=new int[N+1];\n        for(int i=1;i<=N;i++) prefixFreq[i]=prefixFreq[i-1] + frequencyMap[i];\n        \n        long total=0;\n        \n        for(int i=1;i<=N;i++){\n            if(frequencyMap[i]==0) continue;\n            \n            // [i * j, i * (j + 1)) \n                 long sum=0;\n                for(int j=1; i*j<=N;j++){\n                   int lower=i*j-1;\n                   int upper=i*(j+1)-1;\n                   \n                   int count= prefixFreq[Math.min(N,upper)] - prefixFreq[lower]; \n                   \n                    sum+=count*j;;\n                }\n                total=(total + (sum%mod)*frequencyMap[i])%mod;\n        }\n        return (int)total;\n    }\n```\n\n**TimeComplexity:**\n```\n\nFor each divisor i we are considering N/i intervals. where 1<=i<=N\n     T(n) <= N/1 + N/2 + N/3 + .... N/N\n          <=N(1/1 + 1/2 + ...  1/N)\n\t\t  <=N*(logN)\n\t\t  \nIts a worse case because if freq is 0 we are just continuing.. \t\t\n```  \n\nPlease upvote if found it helpful :)\n
['Counting', 'Prefix Sum', 'Java']