Floored pair
Explanation :  \n   Sort the array\n   Find the prefix sum (ps) where the ith element contains number of elements <= i.  \n     For eg. sorted arr -> 1, 1, 2, 5
**Explanation** :  \n*   Sort the array\n*   Find the prefix sum (ps) where the ith element contains number of elements <= i.  \n     For eg. sorted arr -> 1, 1, 2, 5\n\t prefix sum -> 0, 2, 2, 3, 3, 4\n*   Since the array is sorted. Time complexity for finding the floored sum will be O(n)\n               **Reason** : \n\t\t\t\t\tLet\'s take a sorted array : 2, 5, 10, 17, 20, 25, 26, 35\n\t\t\t\t\tFloored sum for (i, j) : Math.floor(arr[j]/arr[i])\n\t\t\t\tfor i = 1 -> | (2/2) <= (5/2) <= (10/2) <= (17/2) <= ..... <= (35/2)\n\t\t\t\tfor i = 2 -> | (5/5) <= (10/5) <= (17/5) <= ...... <= (35/5)\n\t\t\t\t....\n\t\t\t\tfor i = 1 -> minimum floored value is 1 and maximum 17\n\t\t\t\tfor i = 2 -> minimum floored value is 1 and maximum 7\n\t\t\t\t....\n\t\t\t\thence for worst time complexity where the sorted array is 1,2,3,4,5,...,n\n\t\t\t\tfor i = 1 -> minimum floored value is 1 and maximum n\n\t\t\t\tfor i = 2 -> minimum floored value is 1 and maximum (n/2)\n\t\t\t\tfor i = 2 -> minimum floored value is 1 and maximum (n/3)\n\t\t\t\t\n   **Hence**, if we iterate for every i,  from minimum floored value to maximum floored value\n   Time complexity will be ->\n            n + (n/2) + (n/3) + .... + (n/n-1) + 1 = 1 + n * ((1/2) + (1/3) + (1/4) + .... + (1/(n-1))\n\t\t\tfor n = 10^5 \n\t\t\t\t<= 1 + 13n = O(n)\n\t\t\t\t\n\tThus, finding the floored sum follows,\n\t\t\t\tfor any floored value x and arr[i].. find the number of elements in between \n\t\t\t\t                     arr[i] * (x + 1) - 1 and arr[i] * x (which we\'ll get using the ps array)\n\t\t\t\tupdate the sum with the above value multiplied with x\n\t\t\t\t\n\tDo this for all arr[i] and the respective floored sum!!\n\t\n\t\n\tTime complexity -> O(nlogn) (sorting) + O(n) (as discussed above) = O(nlogn)\n\t\t\t\t\n           \t\t\t        \n```\nvar sumOfFlooredPairs = function(nums) {\n    let p = Math.pow(10, 9) + 7;\n    nums.sort((a, b) => (a - b));\n\n    let ps = [0];\n    let sum = 0;\n\n    for (let i = 1; i <= nums[nums.length - 1]; i++) {\n        ps[i] = 0;\n    }\n    for (let i = 0; i < nums.length; i++) {\n        ps[nums[i]]++;\n    }\n    for (let i = 1; i <= nums[nums.length - 1]; i++) {\n        ps[i] = ps[i] + ps[i - 1];\n    }\n\n    let prevSum = 0;\n    for (let i = 0; i < nums.length; i++) {\n\n        if (i > 0 && nums[i] === nums[i - 1]) sum += prevSum;\n        else {\n            prevSum = 0;\n            let flooredValue = Math.floor(nums[nums.length - 1] / nums[i]);\n            for (let j = 1; j <= flooredValue; j++) {\n                let lastIndex = ((nums[i] * (j + 1) - 1) > nums[nums.length - 1] ? nums[nums.length - 1] : (nums[i] * (j + 1) - 1));\n                prevSum += (ps[lastIndex] - ps[(j * nums[i] - 1)]) * j;\n                prevSum %= p;\n            }\n            sum += prevSum;\n        }\n\n        sum %= p;\n    }\n    return sum; \n};\n```
['Math', 'Prefix Sum']