You are given an array of positive integers nums. The task is to compute the sum of floor(nums[i] / nums[j]) for all pairs (i, j) where 0 ≤ i, j < n and floor(x) is the greatest integer less than or equal to x.
In other words, for every ordered pair of elements in nums, calculate the integer division of nums[i] by nums[j], sum up all these values, and return the result modulo 109 + 7.
(i, j) is considered, including when i == j.1 ≤ nums.length ≤ 1051 ≤ nums[i] ≤ 105109 + 7.
At first glance, the problem invites a brute-force approach: for every pair of elements in nums, compute floor(nums[i] / nums[j]) and sum the results. However, with up to 10^5 elements, this would require 10^{10} operations—far too slow.
The key is to observe that the same value may appear many times in nums, and the result of floor(a / b) only depends on the values of a and b, not their positions. Thus, grouping by value and precomputing frequencies can help.
We can also flip the problem: instead of iterating over all pairs, for each possible value of nums[j] (call it x), count how many nums[i] fall into each interval where floor(nums[i] / x) = k for each k. This leads to a counting-based, interval-sweeping approach.
This shift—from pairwise iteration to value-based grouping and prefix sums—enables a much faster solution.
nums. Store this in an array freq of length max(nums) + 1.prefix where prefix[i] is the total number of elements ≤ i in nums.[l, r], prefix[r] - prefix[l-1] gives the count of elements in that range.x that appears in nums (where freq[x] > 0).x, consider all possible quotients k such that floor(a / x) = k.x and k, all a in [k*x, (k+1)*x - 1] will have floor(a / x) = k.a in nums fall into this interval.freq[x] * count * k to the answer.10^9 + 7.
This approach reduces the time complexity to roughly O(N \log N), which is efficient enough for the problem constraints.
Consider nums = [2, 5, 9]. Let's walk through the optimized solution:
This matches the expected answer.
O(N^2) — For each pair, compute floor(a / b).O(1) (apart from input and output).O(N \log N) (or O(N \sqrt{M}) where M is max value in nums), since for each unique value we process its multiples.O(M) for frequency and prefix sum arrays.The optimized method is efficient enough for large inputs.
The Sum of Floored Pairs problem can be solved efficiently by shifting from naive pairwise iteration to a counting strategy using frequency and prefix sums. By grouping elements and using interval sweeps, we avoid redundant calculations and achieve a scalable solution. This approach is a great example of how mathematical insight and careful precomputation can turn an intractable brute-force problem into an elegant and efficient algorithm.
class Solution:
def sumOfFlooredPairs(self, nums):
MOD = 10 ** 9 + 7
max_num = max(nums)
freq = [0] * (max_num + 2)
for num in nums:
freq[num] += 1
prefix = [0] * (max_num + 2)
for i in range(1, max_num + 2):
prefix[i] = prefix[i - 1] + freq[i]
ans = 0
for x in range(1, max_num + 1):
if freq[x] == 0:
continue
k = 1
while x * k <= max_num:
l = x * k
r = min(x * (k + 1) - 1, max_num)
count = prefix[r] - prefix[l - 1]
ans = (ans + freq[x] * count * k) % MOD
k += 1
return ans
class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
const int MOD = 1e9 + 7;
int max_num = *max_element(nums.begin(), nums.end());
vector<int> freq(max_num + 2, 0);
for (int num : nums) freq[num]++;
vector<int> prefix(max_num + 2, 0);
for (int i = 1; i <= max_num + 1; ++i) {
prefix[i] = prefix[i-1] + freq[i];
}
long long ans = 0;
for (int x = 1; x <= max_num; ++x) {
if (freq[x] == 0) continue;
for (int k = 1; x * k <= max_num; ++k) {
int l = x * k;
int r = min(x * (k + 1) - 1, max_num);
int count = prefix[r] - prefix[l - 1];
ans = (ans + 1LL * freq[x] * count * k) % MOD;
}
}
return (int)ans;
}
};
class Solution {
public int sumOfFlooredPairs(int[] nums) {
int MOD = 1000000007;
int maxNum = 0;
for (int num : nums) maxNum = Math.max(maxNum, num);
int[] freq = new int[maxNum + 2];
for (int num : nums) freq[num]++;
int[] prefix = new int[maxNum + 2];
for (int i = 1; i <= maxNum + 1; i++) {
prefix[i] = prefix[i - 1] + freq[i];
}
long ans = 0;
for (int x = 1; x <= maxNum; x++) {
if (freq[x] == 0) continue;
int k = 1;
while (x * k <= maxNum) {
int l = x * k;
int r = Math.min(x * (k + 1) - 1, maxNum);
int count = prefix[r] - prefix[l - 1];
ans = (ans + 1L * freq[x] * count * k) % MOD;
k++;
}
}
return (int)ans;
}
}
var sumOfFlooredPairs = function(nums) {
const MOD = 1e9 + 7;
let maxNum = Math.max(...nums);
let freq = new Array(maxNum + 2).fill(0);
for (let num of nums) freq[num]++;
let prefix = new Array(maxNum + 2).fill(0);
for (let i = 1; i <= maxNum + 1; i++) {
prefix[i] = prefix[i - 1] + freq[i];
}
let ans = 0;
for (let x = 1; x <= maxNum; x++) {
if (freq[x] === 0) continue;
let k = 1;
while (x * k <= maxNum) {
let l = x * k;
let r = Math.min(x * (k + 1) - 1, maxNum);
let count = prefix[r] - prefix[l - 1];
ans = (ans + freq[x] * count * k) % MOD;
k++;
}
}
return ans;
};