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] <= 105Problem Overview: Given an integer array nums, compute the total value of floor(nums[i] / nums[j]) for every pair (i, j). A direct pairwise computation quickly becomes too slow because the array can contain up to 105 values.
Approach 1: Naive Approach Using Nested Loop (Time: O(n²), Space: O(1))
The most direct method checks every ordered pair in the array. Use two nested loops and compute floor(nums[i] / nums[j]) for each pair. Accumulate the result while applying the required modulo. This approach is easy to implement and useful for validating logic on small inputs. However, with n up to 100k, the n² comparisons quickly become infeasible. The method does not use any special data structures and simply iterates through the array twice.
Approach 2: Optimized Counting and Prefix Sum (Time: ~O(M log M), Space: O(M))
The key observation: instead of iterating over pairs, group numbers by value and count how many fall into ranges that produce the same quotient. Build a frequency array for every value in nums. Then compute a prefix sum array so you can quickly query how many numbers lie inside a value range. For a fixed value x, all numbers in the interval [k*x, (k+1)*x - 1] produce floor(num / x) = k. Iterate over multiples of x, use the prefix sum to count elements in each interval, and accumulate k * count * freq[x]. This avoids explicit pair iteration and converts the problem into range counting. The technique relies heavily on math observations and fast range queries using prefix sums.
Recommended for interviews: Interviewers expect the counting + prefix sum solution. The brute force approach demonstrates that you understand the definition of the operation, but the optimized solution shows the real insight: convert pair comparisons into frequency-based range counting. Recognizing quotient ranges and iterating through multiples is the core trick that reduces the runtime enough to pass constraints.
This is the straightforward approach where you loop through all pairs of elements in the array and compute the floor division of each pair. While not efficient for large arrays, it helps understand the problem better.
This C solution employs two nested loops to iterate over each pair in the array and calculates the floor division using the integer division operator. It sums up these floor divisions modulo 10^9 + 7.
Time Complexity: O(n^2) - iterating over each pair of elements.
Space Complexity: O(1) - no additional space required.
This approach involves pre-computation using a counting array to determine the frequency of each element, then using this data to quickly compute sum of floored pairs using properties of division.
The C solution leverages a count array to store the frequency of each number up to the given maximum value (100,000) and prefix sum to allow efficient computation of range sums.
Time Complexity: O(n + max * log(max)) - counting and prefix processing.
Space Complexity: O(max) - space used for count and prefix arrays.
First, we count the occurrences of each element in the array nums and record them in the array cnt. Then, we calculate the prefix sum of the array cnt and record it in the array s, i.e., s[i] represents the count of elements less than or equal to i.
Next, we enumerate the denominator y and the quotient d. Using the prefix sum array, we can calculate the count of the numerator s[min(mx, d times y + y - 1)] - s[d times y - 1], where mx represents the maximum value in the array nums. Then, we multiply the count of the numerator by the count of the denominator cnt[y], and then multiply by the quotient d. This gives us the value of all fractions that meet the conditions. By summing these values, we can get the answer.
The time complexity is O(M times log M), and the space complexity is O(M). Here, M is the maximum value in the array nums.
| Approach | Complexity |
|---|---|
| Naive Approach Using Nested Loop | Time Complexity: O(n^2) - iterating over each pair of elements. |
| Optimized Approach Using Counting and Prefix Sum | Time Complexity: O(n + max * log(max)) - counting and prefix processing. |
| Prefix Sum of Value Range + Optimized Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Nested Loop | O(n²) | O(1) | Small input sizes or verifying correctness during development |
| Counting + Prefix Sum Optimization | ~O(M log M) | O(M) | Large arrays where value range is bounded; required for passing competitive programming constraints |
Sum of Floored Pairs | Prefix Sum | Sieve Technique | Leetcode Hard | 1862 LeetCode • CodeWithSunny • 2,034 views views
Watch 4 more video solutions →Practice Sum of Floored Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor