Solution Explanation for Sum of Floored Pairs

This problem asks to calculate the sum of floor(nums[i] / nums[j]) for all pairs of indices (i, j) in the input array nums. A naive approach with nested loops would result in O(n^2) time complexity, which is inefficient for larger input arrays. The optimal solution uses a clever approach combining counting, prefix sums, and optimized enumeration to achieve significantly better performance.

Approach: Prefix Sum and Optimized Enumeration

The solution leverages the following observations:

1. Counting Element Frequencies: We first count the frequency of each number in nums using a Counter (Python) or a similar data structure. This allows us to efficiently access the number of times a specific number appears.

2. Prefix Sum: A prefix sum array s is created. s[i] stores the total count of numbers in nums that are less than or equal to i. This enables us to quickly find the number of elements within a given range.

3. Optimized Enumeration: Instead of brute-forcing all pairs (i, j), we iterate through possible denominators (y from nums) and quotients (d). For each y and d, we use the prefix sum array s to efficiently count the number of numerators (x in nums) that satisfy d * y <= x < (d + 1) * y. The number of such numerators is given by s[min(mx, d * y + y - 1)] - s[d * y - 1], where mx is the maximum value in nums.

4. Calculating the Sum: For each valid combination of y and d, we add the contribution cnt[y] * d * (number of numerators) to the total sum, where cnt[y] is the count of the denominator y. The modulo operation (% 1000000007) is applied throughout to prevent integer overflow.

Time and Space Complexity Analysis

• Time Complexity: The outer loop iterates up to mx (maximum value in nums), and the inner loop iterates at most mx / y times for each y. In the worst case (all numbers are 1), the inner loop dominates, leading to approximately O(mx * log(mx)). Since mx is bounded by 10^5, this complexity is effectively O(M log M), where M is the maximum value in the array. Creating the prefix sum array and counting frequencies takes O(M) time.

• Space Complexity: We use arrays cnt and s, both of size mx + 1, resulting in O(M) space complexity.

Code Examples (Python)

from collections import Counter
 
class Solution:
    def sumOfFlooredPairs(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        cnt = Counter(nums)
        mx = max(nums)
        s = [0] * (mx + 1)
        for i in range(1, mx + 1):
            s[i] = s[i - 1] + cnt[i]
        ans = 0
        for y in range(1, mx + 1):
            if cnt[y]:
                d = 1
                while d * y <= mx:
                    ans += cnt[y] * d * (s[min(mx, d * y + y - 1)] - s[d * y - 1])
                    ans %= mod
                    d += 1
        return ans
 

The code in other languages (Java, C++, Go, TypeScript, Rust) follows a very similar structure, reflecting the same algorithmic approach. The core idea remains the same: utilizing prefix sums and an optimized enumeration strategy to avoid the quadratic time complexity of a naive solution.