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:
10
Time Compexity: O(nlog(n))