Sum of Floored Pairs
HardPrompt
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 <= 1051 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward solution is to simulate the process directly. We can use nested loops to iterate through every possible pair of indices (i, j) in the nums array. For each pair, we calculate floor(nums[i] / nums[j]) and add it to a running total.
Algorithm
- Initialize
totalSum = 0LandMOD = 10^9 + 7. - Iterate
ifrom0tonums.length - 1. - Iterate
jfrom0tonums.length - 1. -
Calculate `quotient = nums[i] / nums[j]`. -
Add `quotient` to `totalSum`. - Return
(int)(totalSum % MOD).
Walkthrough
We initialize a variable sum to zero. We then set up two nested loops, both iterating from 0 to nums.length - 1. The outer loop variable can be i and the inner loop variable j. Inside the inner loop, we compute the integer division nums[i] / nums[j] and add the result to sum. To handle the large potential sum, we should use a long for the sum variable. The final result is this sum modulo 10^9 + 7.
class Solution { public int sumOfFlooredPairs(int[] nums) { long totalSum = 0; int MOD = 1_000_000_007; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) { if (nums[j] != 0) { // Although constraints say nums[i] >= 1, good practice. totalSum += nums[i] / nums[j]; } } } return (int)(totalSum % MOD); }}Complexity
Time
O(N^2), where N is the length of `nums`. With N up to 10^5, this is approximately 10^10 operations, which is too slow.
Space
O(1), as we only use a few variables to store the sum and loop counters.
Trade-offs
Pros
Very simple to understand and implement.
Requires no extra space.
Cons
Highly inefficient for the given constraints and will result in a Time Limit Exceeded (TLE) error.
The brute-force approach performs many redundant calculations if the input array contains duplicate numbers. For example, if nums = [2, 2, 5], the calculation for floor(5/2) is done twice. We can optimize this by first counting the occurrences of each unique number.
Algorithm
- Find the maximum value
maxValinnums. - Create a frequency array
countsof sizemaxVal + 1and populate it. - Initialize
totalSum = 0LandMOD = 10^9 + 7. - Iterate
xfrom1tomaxVal.- If
counts[x] == 0, continue. - Iterate
yfrom1tomaxVal.- If
counts[y] == 0, continue. - Calculate
quotient = x / y. - Calculate
contribution = (long)counts[x] * counts[y] * quotient. - Update
totalSum = (totalSum + contribution) % MOD.
- If
- If
- Return
(int)totalSum.
Walkthrough
We can express the total sum as Σ (count(x) * count(y) * floor(x / y)) for all unique pairs of numbers (x, y) present in the array.
- First, find the maximum value
maxValinnums. - Create a frequency array
countsof sizemaxVal + 1and populate it by iterating throughnums. - Then, use two nested loops to iterate through all possible pairs of values
(x, y)from1tomaxVal. - If both
xandyare present in the original array (i.e.,counts[x] > 0andcounts[y] > 0), we calculate their contribution to the total sum, which iscounts[x] * counts[y] * (x / y). - We add this contribution to a running total, taking the modulo at each step.
class Solution { public int sumOfFlooredPairs(int[] nums) { int MOD = 1_000_000_007; int maxVal = 0; for (int num : nums) { maxVal = Math.max(maxVal, num); } int[] counts = new int[maxVal + 1]; for (int num : nums) { counts[num]++; } long totalSum = 0; for (int x = 1; x <= maxVal; x++) { if (counts[x] == 0) continue; for (int y = 1; y <= maxVal; y++) { if (counts[y] == 0) continue; long quotient = x / y; long contribution = (long)counts[x] * counts[y] * quotient; totalSum = (totalSum + contribution) % MOD; } } return (int)totalSum; }}Complexity
Time
O(N + M^2), where N is `nums.length` and M is `max(nums)`. Populating the frequency array takes O(N). The nested loops run up to M*M times. With M up to 10^5, M^2 is 10^10, which is still too slow.
Space
O(M) to store the frequency counts, where M is the maximum value in `nums`.
Trade-offs
Pros
More efficient than pure brute-force if N is much larger than M (the maximum value).
Cons
The O(M^2) complexity makes it too slow for the given constraints on the values in
nums.
This approach improves upon the previous methods by first counting the frequency of each number and then changing the perspective of the summation. Instead of iterating through all pairs (nums[i], nums[j]), we iterate through each possible divisor y and for each y, we efficiently calculate the sum of floor(x / y) over all numbers x present in the input array. This efficient calculation is achieved by grouping numbers x that yield the same quotient k = floor(x / y) and using a prefix sum array on the frequencies to quickly find the count of numbers in any range.
Algorithm
- Find the maximum value
maxValinnums. - Create a frequency array
countsof sizemaxVal + 1and populate it by iterating throughnums. - Create a prefix sum array
prefixCountsof sizemaxVal + 1from thecountsarray. - Initialize
totalSum = 0andMOD = 10^9 + 7. - Loop for
yfrom1tomaxVal:- If
counts[y] == 0, continue. - Initialize
sumForY = 0. - Loop for
mfromytomaxValwith a step ofy(i.e.,m = y, 2y, 3y, ...):- Calculate quotient
k = m / y. - Define the upper bound of the range:
upper = m + y - 1. - Find the count of numbers in
numswithin the range[m, upper]:countInRange = prefixCounts[min(upper, maxVal)] - prefixCounts[m - 1]. - Add the contribution to
sumForY:sumForY = (sumForY + (long)k * countInRange) % MOD.
- Calculate quotient
- Add the total contribution for divisor
ytototalSum:totalSum = (totalSum + (long)counts[y] * sumForY) % MOD.
- If
- Return
totalSum.
Walkthrough
- First, we determine the maximum value (
maxVal) in thenumsarray. - We create a frequency array,
counts, of sizemaxVal + 1to store the count of each number innums. - We then create a prefix sum array,
prefixCounts, also of sizemaxVal + 1.prefixCounts[i]will store the total count of numbers innumsthat are less than or equal toi. This allows us to find the count of numbers in any range[a, b]inO(1)time usingprefixCounts[b] - prefixCounts[a-1]. - The main logic iterates through each possible divisor
yfrom1tomaxVal. We only proceed ifyis actually present in the input array (i.e.,counts[y] > 0). - For each such divisor
y, we calculatesum_for_y = Σ_x counts[x] * floor(x/y). To do this efficiently, we iterate through multiples ofy. For each multiplem = k * y, all numbersxin the range[m, m + y - 1]havefloor(x/y) = k. - We use the
prefixCountsarray to find how many numbers from the originalnumsarray fall into this range. Let this becount_in_range. - The contribution to
sum_for_yfrom this range isk * count_in_range. We sum these contributions for allk. - The total contribution to the final answer for the divisor
yiscounts[y] * sum_for_y. - We sum up these contributions for all
yto get the final result, taking the modulo at each step to prevent overflow.
class Solution { public int sumOfFlooredPairs(int[] nums) { int MOD = 1_000_000_007; int maxVal = 0; for (int num : nums) { maxVal = Math.max(maxVal, num); } int[] counts = new int[maxVal + 1]; for (int num : nums) { counts[num]++; } long[] prefixCounts = new long[maxVal + 1]; for (int i = 1; i <= maxVal; i++) { prefixCounts[i] = prefixCounts[i - 1] + counts[i]; } long totalSum = 0; for (int y = 1; y <= maxVal; y++) { if (counts[y] == 0) { continue; } long sumForY = 0; for (long m = y; m <= maxVal; m += y) { long k = m / y; int upper = (int)Math.min(m + y - 1, maxVal); long countInRange = prefixCounts[upper] - prefixCounts[(int)m - 1]; sumForY = (sumForY + k * countInRange) % MOD; } totalSum = (totalSum + (long)counts[y] * sumForY) % MOD; } return (int)totalSum; }}Complexity
Time
O(N + M * log(M)), where N is the length of `nums` and M is the maximum value in `nums`. Populating `counts` and `prefixCounts` takes O(N + M). The nested loops' complexity is Σ_{y=1 to M} (M/y), which is the Harmonic series, approximately M * log(M).
Space
O(M) for the `counts` and `prefixCounts` arrays, where M is the maximum value in `nums`.
Trade-offs
Pros
Efficient enough to pass the given constraints.
Correctly handles all cases by leveraging number theory concepts (sum over multiples).
Cons
Requires O(M) extra space, which could be large if the maximum value is large.
The logic is more involved than simpler approaches.
Solutions
Solution
class Solution {public int sumOfFlooredPairs(int[] nums) { final int mod = (int)1 e9 + 7; int mx = 0; for (int x : nums) { mx = Math.max(mx, x); } int[] cnt = new int[mx + 1]; int[] s = new int[mx + 1]; for (int x : nums) { ++cnt[x]; } for (int i = 1; i <= mx; ++i) { s[i] = s[i - 1] + cnt[i]; } long ans = 0; for (int y = 1; y <= mx; ++y) { if (cnt[y] > 0) { for (int d = 1; d * y <= mx; ++d) { ans += 1L * cnt[y] * d * (s[Math.min(mx, d * y + y - 1)] - s[d * y - 1]); ans %= mod; } } } return (int)ans; }}class Solution {public: int sumOfFlooredPairs(vector<int> &nums) { const int mod = 1e9 + 7; int mx = *max_element(nums.begin(), nums.end()); vector<int> cnt(mx + 1); vector<int> s(mx + 1); for (int x : nums) { ++cnt[x]; } for (int i = 1; i <= mx; ++i) { s[i] = s[i - 1] + cnt[i]; } long long ans = 0; for (int y = 1; y <= mx; ++y) { if (cnt[y]) { for (int d = 1; d * y <= mx; ++d) { ans += 1LL * cnt[y] * d * (s[min(mx, d * y + y - 1)] - s[d * y - 1]); ans %= mod; } } } return ans; }};class Solution: def sumOfFlooredPairs(self, nums: List[int]) -> int: mod = 10 ** 9 + 7 cnt = Counter(nums) mx = max(nums) s = [0] * (mx + 1) for i in range(1, mx + 1): s[i] = s[i - 1] + cnt[i] ans = 0 for y in range(1, mx + 1): if cnt[y]: d = 1 while d * y <= mx: ans += cnt[y] * d * (s[min(mx, d * y + y - 1)] - s[d * y - 1]) ans %= mod d += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.