Python3 - thinking process
At the first glance, I would just sort all the elements in order, then iterate for each element nums[i]: increment a factor j from 1, binary search the left bou
At the first glance, I would just sort all the elements in order, then iterate for each element `nums[i]`: increment a factor `j` from 1, binary search the left boundary of `j * nums[i]`, and the right boundary of `(1 + j) * nums[i] - 1`. This is because all the elements in this range will contribute `j` to the final answer. \nThis approach passed almost all the test cases, but got a TLE for a long repeated test case.\n\n**TLE**\n```python\nclass Solution:\n    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n        MOD = 10**9 + 7\n        nums.sort()\n        n = len(nums)\n        maxi = max(nums)\n        ans = 0\n        for i in range(n):\n            j = 1\n            while j * nums[i] <= maxi:\n                left = bisect.bisect_left(nums, j * nums[i])\n                right = bisect.bisect_right(nums, (j + 1) * nums[i] - 1)\n                ans += j * (right - left)\n                j += 1\n        return ans % MOD\n```\n\nSo it looks like we should just keep the freqency of the elements, instead of the original nums array. But how do we get how many elements are in the range of `j * nums[i]` to `(1 + j) * nums[i] - 1`? We need some other ways to get all the elements in that range. \n\nAlso, notice that binary search is very time consuming. If we could cache those bounary results, we should not need to do binary searches. We can use prefix array to memorize the number of elements smaller than a particular element. In this way, we can use a simple array access O(1) as opposed to binary search O(log(n)) to quickly figure out\n\n1. how many elements are smaller than `(1 + j) * nums[i] - 1`; and\n2. how many elements smaller than `j * nums[i]` as well). \n\nTake the difference between the above 2 cases, we know how many elements are within that range. \n\nIn the actual implementation, we did it in the reverse way - for each `num` we count how many elements are greater than `j * nums[i]`, since the last group of elements (with the biggest valid `j`) always contribute the most `count[num]` to the answer.\n\n**Final solution**\n```python\nclass Solution:\n    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n        MOD = 10**9 + 7\n        count = Counter(nums)\n        n = len(nums)\n        maxi = max(nums)\n        ans = 0\n        \n        prefix = [0]\n        for i in range(1, maxi + 1):\n            prefix += prefix[-1] + count[i],\n\n        for num in set(nums):\n            for i in range(num, maxi + 1, num):\n                ans += count[num] * (prefix[-1] - prefix[i-1])\n        return ans % MOD\n```
[]