Skip to content

1862. Sum of Floored Pairs

Difficulty Topics

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

Solution

sum-of-floored-pairs.py
class Solution:
    def sumOfFlooredPairs(self, nums: List[int]) -> int:
        M = 10 ** 9 + 7

        prefix = [0] * (max(nums) + 1)
        counter = collections.Counter(nums)

        for num, count in counter.items():
            for j in range(num, len(prefix), num):
                prefix[j] += count

        for i in range(1, len(prefix)):
            prefix[i] += prefix[i - 1]

        return sum(prefix[num] for num in nums) % M
sum-of-floored-pairs.cpp
class Solution {
public:
    const int MAXN = 1e5 + 1, MOD = 1e9 + 7;
    int sumOfFlooredPairs(vector<int>& nums) {
        vector<long> freq(2*MAXN+1);        
        long mx = 0, sum = 0;
        for(auto num : nums) ++freq[num], mx = max((int)mx, num);  // counting frequency of each element in nums
        for(int i = 1; i <= 2*MAXN; ++i) freq[i] += freq[i - 1];   // building prefix sum array of freq. Now freq[i] will hold the frequency of numbers less than or equal to i
        // Each num will be assumed in the denominator as floor(nums[i] / num) and 
        // using freq array, we can calculate the number of terms contributing 1, 2, 3... to the sum each.
        for(auto num : nums) { 
            long l = num, r = 2 * num - 1, divResult = 1;
            while(l <= mx) {                
                sum = (sum + divResult * (freq[r] - freq[l - 1])) % MOD;
                l += num, r += num;
                ++divResult;
            }
        }
        return sum;
    }
};