⚡| python | highly optimized | O(n + m. logm)| Beats 100%| ⚡
Intuition\nRather than checking every pair (i, j), we use the frequency of each number and cumulative sums to compute the result in a more efficient way, reduci
# Intuition\nRather than checking every pair (i, j), we use the frequency of each number and cumulative sums to compute the result in a more efficient way, reducing the need for nested loops.\n# Approach\nWe optimize the problem using frequency counting and prefix sums. Instead of checking every pair, we first count how many times each number appears in nums using a frequency array. Then, we create a prefix sum array to store cumulative counts up to each number. This helps us efficiently calculate the sum of floored divisions without iterating over all pairs directly.\n\n# Complexity\n- Time complexity:\nO(n+m\u22C5logm), where n is the size of nums, and \uD835\uDC5A is the maximum number in nums. This is because we build the frequency and prefix arrays and then use them to calculate the floored sums.\n\n- Space complexity:\nO(m), where \uD835\uDC5A is the maximum value in nums. We need space for the frequency and prefix sum arrays, each of size \uD835\uDC5A + 1\n\n# Code\n```python []\nclass Solution:\n    def sumOfFlooredPairs(self, nums):\n        MOD = 10**9 + 7\n        max_val = max(nums)\n        \n        # Step 1: Create a frequency array\n        freq = [0] * (max_val + 1)\n        for num in nums:\n            freq[num] += 1\n        \n        # Step 2: Create a prefix sum of the frequency array\n        prefix = [0] * (max_val + 1)\n        for i in range(1, max_val + 1):\n            prefix[i] = prefix[i - 1] + freq[i]\n        \n        # Step 3: Calculate the sum of floored pairs\n        result = 0\n        for x in range(1, max_val + 1):\n            if freq[x] > 0:  # Only process if x exists in nums\n                for k in range(1, (max_val // x) + 1):\n                    lower = k * x\n                    upper = min(max_val, (k + 1) * x - 1)\n                    result += freq[x] * k * (prefix[upper] - prefix[lower - 1])\n                    result %= MOD\n        \n        return result\n\n```
['Python']