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

/**
 * @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;
};