Sum of Floored Pairs

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.
The floor() function returns the integer part of the division.

Examples:

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.

Input: nums = [7,7,7,7,7,7,7]
Output: 49

Approach:
We need to observe that the result of floor(nums[i] / nums[j]), will be –

0 if nums[i] < nums[j]
1 if nums[j] <= nums[i] < (2 * nums[j])
2 if 2 * nums[j] <= nums[i] < (3 * nums[j])
and so on…

We can use this to build a frequency array and then calculate the prefix sum of it.

After this, for every num in nums, we will add the answer into sum as per the above observation.

All the numbers in the range [0, num – 1] will contribute 0 to the sum each. The frequency of numbers in this range will be given by freq[num – 1] – freq[0].
All the numbers in the range [num, 2*num – 1] will contribute 1 to the sum each. Frequency: freq[num] – freq[2num – 1].
Numbers in [2*num, 3*num – 1] will contribute 3 each. Frequency: freq[2num] – freq[3num – 1].
And so on till our range covers the maximum element of the nums array…

Implementation in C++:

#include<bits/stdc++.h>
#include <iostream>

using namespace std;
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;
}

int main() {
  vector < int > g1;
  g1.push_back(2);
  g1.push_back(5);
  g1.push_back(9);
  int ans = sumOfFlooredPairs(g1);
  cout << ans << "\n";
  return 0;
}

Output:

Time Compexity: O(nlog(n))