1862. Sum of Floored Pairs
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 109 + 7
.
The floor()
function returns the integer part of the division.
Example 1:
Input: nums = [2,5,9] Output: 10 Explanation: floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0 floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1 floor(5 / 2) = 2 floor(9 / 2) = 4 floor(9 / 5) = 1 We calculate the floor of the division for every pair of indices in the array then sum them up.
Example 2:
Input: nums = [7,7,7,7,7,7,7] Output: 49
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
Solutions
Solution: Prefix Sum + Math
- Time complexity: O(n+Max(nums)logMax(nums))
- Space complexity: O(Max(nums))
JavaScript
js
/**
* @param {number[]} nums
* @return {number}
*/
const sumOfFlooredPairs = function (nums) {
const MODULO = 10 ** 9 + 7;
const maxNum = Math.max(...nums);
const prefixCounts = Array.from({ length: maxNum + 1 }, () => 0);
let result = 0;
for (const num of nums) {
prefixCounts[num] += 1;
}
for (let num = 1; num <= maxNum; num++) {
prefixCounts[num] += prefixCounts[num - 1];
}
for (let denominator = 1; denominator <= maxNum; denominator++) {
const count = prefixCounts[denominator] - prefixCounts[denominator - 1];
if (!count) continue;
let sum = 0;
for (let floored = 1; floored * denominator <= maxNum; floored++) {
const low = floored * denominator;
const high = Math.min(maxNum, (floored + 1) * denominator - 1);
const totalCount = prefixCounts[high] - prefixCounts[low - 1];
sum = (sum + totalCount * floored) % MODULO;
}
result = (result + sum * count) % MODULO;
}
return result;
};