Sum of Floored Pairs
01 · Problem
You are given an array of positive integers nums. Compute the sum of floor(nums[i] / nums[j]) over all ordered pairs of indices (i, j) with 0 <= i, j < nums.length, including pairs where i == j.
Because the total can be very large, return it modulo 10^9 + 7.
02 · Examples
nums = [2,5,9]
10
The pairs give floor(2/2)=1, floor(2/5)=0, floor(2/9)=0, floor(5/2)=2, floor(5/5)=1, floor(5/9)=0, floor(9/2)=4, floor(9/5)=1, floor(9/9)=1. Their total is 10.
nums = [7,7,7,7,7,7,7]
49
Every one of the 7 * 7 = 49 ordered pairs contributes floor(7/7) = 1.
nums = [1,2,3]
9
Dividing everything by 1 gives 1 + 2 + 3 = 6, dividing by 2 gives 0 + 1 + 1 = 2, and dividing by 3 gives 0 + 0 + 1 = 1. The total is 9.
03 · Constraints
- 011 <= nums.length <= 105
- 021 <= nums[i] <= 105
- 03Pairs (i, j) include i == j, and the sum is returned modulo 109 + 7
04 · Optimal complexity
- Time
- O(n + M log M)
- Space
- O(M)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.