Sum of Floored Pairs

Problem Description

Given an integer array nums, return the sum of floor(nums[i] / nums[j]) for all pairs of indices 0 <= i, j < nums.length in the array. Since the answer may be too large, return it modulo 10^9 + 7.

Key Insights

• The brute force approach of iterating through all pairs would result in O(n^2) time complexity, which is inefficient for large n.
• Instead of calculating the floor division for each pair individually, we can leverage the properties of division and counting occurrences.
• For each possible divisor (from 1 to the maximum element in nums), we can determine how many elements in nums are divisible by it.
• Using this information, we can calculate contributions to the result in a more efficient manner.

Space and Time Complexity

Time Complexity: O(n + max(nums))
Space Complexity: O(max(nums))

Solution

To solve the problem, we can use the following approach:

1. Create a frequency array to count occurrences of each number in nums.
2. Iterate over all possible values, and for each value, calculate how many pairs contribute to the sum using the frequency array.
3. For each divisor d, count how many numbers in nums are greater than or equal to d, which determines how many times floor(nums[i] / d) contributes to the total sum.
4. Sum these contributions and return the result modulo 10^9 + 7.

Code Solutions