Sum of Floored Pairs solution and explanation
4 more videos on this problem
Sum of Floored Pairs | Prefix Sum | Sieve Technique | Leetcode Hard | 1862 LeetCodeCodeWithSunny · 13:24 · 2K views
LeetCode 1862. Sum of Floored PairsHappy Coding · 17:46 · 1K views
1862. Sum of Floored Pairs (Leetcode Hard)Programming Live with Larry · 36:16 · 553 views
【每日一题】1862. Sum of Floored Pairs, 5/19/2021Huifeng Guan · 23:36 · 344 views
[outdated: read description] Biweekly 52 Q4: Sum of floored pairs [hard]Daily Dose of LeetCode · 23:30 · 221 views
The problem
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
Approach overview
Problem 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.
Approach 1: Naive Approach Using Nested Loop
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.
def sum_of_floored_pairs(nums):
result = 0
mod = 10**9 + 7
for i in range(len(nums)):
for j in range(len(nums)):
result += nums[i] // nums[j]
result %= mod
return result
print(sum_of_floored_pairs([2, 5, 9]))import java.util.*;
public class Solution {
public static int sumOfFlooredPairs(int[] nums) {
long result = 0;
int mod = 1000000007;
for (int i = 0; i < nums.length; ++i) {
for (int j = 0; j < nums.length; ++j) {
result += nums[i] / nums[j];
result %= mod;
}
}
return (int) result;
}
public static void main(String[] args) {
int[] nums = {2, 5, 9};
System.out.println(sumOfFlooredPairs(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
#define MOD 1000000007
int sumOfFlooredPairs(vector<int>& nums) {
long long result = 0;
int size = nums.size();
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
result += (nums[i] / nums[j]);
result %= MOD;
}
}
return static_cast<int>(result);
}
int main() {
vector<int> nums = {2, 5, 9};
cout << sumOfFlooredPairs(nums) << endl;
return 0;
}function sumOfFlooredPairs(nums) {
let result = 0;
const mod = 1000000007;
for (let i = 0; i < nums.length; ++i) {
for (let j = 0; j < nums.length; ++j) {
result += Math.floor(nums[i] / nums[j]);
result %= mod;
}
}
return result;
}
console.log(sumOfFlooredPairs([2, 5, 9]));#include <stdio.h>
#define MOD 1000000007
int sumOfFlooredPairs(int* nums, int numsSize) {
long long result = 0;
for (int i = 0; i < numsSize; ++i) {
for (int j = 0; j < numsSize; ++j) {
result += (nums[i] / nums[j]);
result %= MOD;
}
}
return (int)result;
}
int main() {
int nums[] = {2, 5, 9};
int result = sumOfFlooredPairs(nums, 3);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public static int SumOfFlooredPairs(int[] nums) {
long result = 0;
int mod = 1000000007;
for (int i = 0; i < nums.Length; ++i) {
for (int j = 0; j < nums.Length; ++j) {
result += nums[i] / nums[j];
result %= mod;
}
}
return (int)result;
}
public static void Main(string[] args) {
int[] nums = {2, 5, 9};
Console.WriteLine(SumOfFlooredPairs(nums));
}
}This Python solution uses two nested loops to process each pair, calculates the floor division and updates the result modulo 10^9 + 7.
Time Complexity: O(n^2) - a double loop over the array.
Space Complexity: O(1) - no additional space storage.
Approach 2: Optimized Approach Using Counting and Prefix Sum
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.
def sum_of_floored_pairs(nums):
max_val = 100000
mod = 10**9 + 7
count = [0] * (max_val + 1)
for num in nums:
count[num] += 1
prefix = [0] * (max_val + 1)
for i in range(1, max_val + 1):
prefix[i] = prefix[i - 1] + count[i]
result = 0
for i in range(1, max_val + 1):
if count[i] > 0:
for j in range(i, max_val + 1, i):
high = min(j + i - 1, max_val)
sum_count = prefix[high] - prefix[j - 1]
result += count[i] * (j // i) * sum_count
result %= mod
return result
print(sum_of_floored_pairs([2, 5, 9]))public class Solution {
public static int sumOfFlooredPairs(int[] nums) {
int max = 100000;
int mod = 1000000007;
int[] count = new int[max + 1];
for (int num : nums) {
count[num]++;
}
int[] prefixSum = new int[max + 1];
for (int i = 1; i <= max; ++i) {
prefixSum[i] = prefixSum[i - 1] + count[i];
}
long result = 0;
for (int i = 1; i <= max; ++i) {
if (count[i] > 0) {
for (int j = i; j <= max; j += i) {
int high = Math.min(j + i - 1, max);
int sumCount = prefixSum[high] - prefixSum[j - 1];
result += (long) count[i] * (j / i) * sumCount;
result %= mod;
}
}
}
return (int) result;
}
public static void main(String[] args) {
int[] nums = {2, 5, 9};
System.out.println(sumOfFlooredPairs(nums));
}
}#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 100000
#define MOD 1000000007
int sumOfFlooredPairs(vector<int>& nums) {
vector<int> count(MAX + 1, 0);
for (int num : nums) {
count[num]++;
}
vector<int> prefixSum(MAX + 1, 0);
for (int i = 1; i <= MAX; ++i) {
prefixSum[i] = prefixSum[i - 1] + count[i];
}
long long result = 0;
for (int i = 1; i <= MAX; ++i) {
if (count[i] > 0) {
for (int j = i; j <= MAX; j += i) {
int high = min(j + i - 1, MAX);
int sumCount = prefixSum[high] - prefixSum[j - 1];
result += (long long) count[i] * (j / i) * sumCount;
result %= MOD;
}
}
}
return static_cast<int>(result);
}
int main() {
vector<int> nums = {2, 5, 9};
cout << sumOfFlooredPairs(nums) << endl;
return 0;
}function sumOfFlooredPairs(nums) {
const max = 100000;
const mod = 1000000007;
const count = new Array(max + 1).fill(0);
nums.forEach(num => count[num]++);
const prefix = new Array(max + 1).fill(0);
for (let i = 1; i <= max; ++i) {
prefix[i] = prefix[i - 1] + count[i];
}
let result = 0;
for (let i = 1; i <= max; ++i) {
if (count[i] > 0) {
for (let j = i; j <= max; j += i) {
let high = Math.min(j + i - 1, max);
let sumCount = prefix[high] - prefix[j - 1];
result += count[i] * Math.floor(j / i) * sumCount;
result %= mod;
}
}
}
return result;
}
console.log(sumOfFlooredPairs([2, 5, 9]));#include <stdio.h>
#include <string.h>
#define MAX 100000
#define MOD 1000000007
int sumOfFlooredPairs(int* nums, int numsSize) {
int count[MAX + 1];
memset(count, 0, sizeof(count));
for (int i = 0; i < numsSize; ++i) {
count[nums[i]]++;
}
int prefixSum[MAX + 1];
prefixSum[0] = 0;
for (int i = 1; i <= MAX; ++i) {
prefixSum[i] = prefixSum[i - 1] + count[i];
}
long long result = 0;
for (int i = 1; i <= MAX; ++i) {
if (count[i] > 0) {
for (int j = i; j <= MAX; j += i) {
int high = j + i - 1;
if (high > MAX) high = MAX;
int sumCount = prefixSum[high] - prefixSum[j - 1];
result += (long long) count[i] * (j / i) * sumCount;
result %= MOD;
}
}
}
return (int)result;
}
int main() {
int nums[] = {2, 5, 9};
int result = sumOfFlooredPairs(nums, 3);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public static int SumOfFlooredPairs(int[] nums) {
int max = 100000;
int mod = 1000000007;
int[] count = new int[max + 1];
foreach (var num in nums) {
count[num]++;
}
int[] prefixSum = new int[max + 1];
for (int i = 1; i <= max; ++i) {
prefixSum[i] = prefixSum[i - 1] + count[i];
}
long result = 0;
for (int i = 1; i <= max; ++i) {
if (count[i] > 0) {
for (int j = i; j <= max; j += i) {
int high = Math.Min(j + i - 1, max);
int sumCount = prefixSum[high] - prefixSum[j - 1];
result += (long) count[i] * (j / i) * sumCount;
result %= mod;
}
}
}
return (int)result;
}
public static void Main(string[] args) {
int[] nums = {2, 5, 9};
Console.WriteLine(SumOfFlooredPairs(nums));
}
}Python differs only slightly in syntax from pseudocode yet achieves the same counting and prefix computation strategy.
Time Complexity: O(n + max * log(max)) because of efficient pre-computation.
Space Complexity: O(max) due to additional arrays.
Approach 3: Prefix Sum of Value Range + Optimized Enumeration
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.
function sumOfFlooredPairs(nums: number[]): number {
const mx = Math.max(...nums);
const cnt: number[] = Array(mx + 1).fill(0);
const s: number[] = Array(mx + 1).fill(0);
for (const x of nums) {
++cnt[x];
}
for (let i = 1; i <= mx; ++i) {
s[i] = s[i - 1] + cnt[i];
}
let ans = 0;
const mod = 1e9 + 7;
for (let y = 1; y <= mx; ++y) {
if (cnt[y]) {
for (let d = 1; d * y <= mx; ++d) {
ans += cnt[y] * d * (s[Math.min((d + 1) * y - 1, mx)] - s[d * y - 1]);
ans %= mod;
}
}
}
return ans;
}func sumOfFlooredPairs(nums []int) (ans int) {
mx := slices.Max(nums)
cnt := make([]int, mx+1)
s := make([]int, mx+1)
for _, x := range nums {
cnt[x]++
}
for i := 1; i <= mx; i++ {
s[i] = s[i-1] + cnt[i]
}
const mod int = 1e9 + 7
for y := 1; y <= mx; y++ {
if cnt[y] > 0 {
for d := 1; d*y <= mx; d++ {
ans += d * cnt[y] * (s[min((d+1)*y-1, mx)] - s[d*y-1])
ans %= mod
}
}
}
return
}impl Solution {
pub fn sum_of_floored_pairs(nums: Vec<i32>) -> i32 {
const MOD: i32 = 1_000_000_007;
let mut mx = 0;
for &x in nums.iter() {
mx = mx.max(x);
}
let mut cnt = vec![0; (mx + 1) as usize];
let mut s = vec![0; (mx + 1) as usize];
for &x in nums.iter() {
cnt[x as usize] += 1;
}
for i in 1..=mx as usize {
s[i] = s[i - 1] + cnt[i];
}
let mut ans = 0;
for y in 1..=mx as usize {
if cnt[y] > 0 {
let mut d = 1;
while d * y <= (mx as usize) {
ans += ((cnt[y] as i64)
* (d as i64)
* (s[std::cmp::min(mx as usize, d * y + y - 1)] - s[d * y - 1]))
% (MOD as i64);
ans %= MOD as i64;
d += 1;
}
}
}
ans as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach Using Nested Loop | Time Complexity: O(n^2) - a double loop over the array. |
| Optimized Approach Using Counting and Prefix Sum | Time Complexity: O(n + max * log(max)) because of efficient pre-computation. |
| Prefix Sum of Value Range + Optimized Enumeration | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Sum of Floored Pairs easy or hard?
Sum of Floored Pairs is classified as a hard problem. The difficulty comes from recognizing that direct pair iteration is too slow and discovering the mathematical observation that floor division results form predictable value ranges. Efficient solutions rely on counting and prefix sum techniques.
Sum of Floored Pairs Python/Java solution
Most implementations follow the same structure across languages: build a frequency array, compute prefix sums, iterate through multiples of each value, and accumulate contributions modulo 1e9+7. This approach works efficiently in Python, Java, C++, and other languages because the heavy work is done with array indexing.
How to solve Sum of Floored Pairs in O(n)?
A strict O(n) solution is not typical because the algorithm depends on the maximum value range. The closest practical optimization uses a frequency array and prefix sums, then iterates through multiples of each number. This reduces the work to about O(M log M), which performs efficiently for constraints where M ≤ 100000.
What is the best approach for Sum of Floored Pairs?
The best approach uses frequency counting combined with a prefix sum array. Instead of evaluating every pair, group numbers by value and count how many fall in ranges that produce the same floor division result. Iterating through multiples of each value allows computing contributions efficiently in about O(M log M) time.
Is Sum of Floored Pairs asked at Google/Amazon/Meta?
Hard array and math problems involving counting tricks and prefix sums frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the technique of grouping values and computing contributions through ranges is a common interview pattern.
What data structure is used in Sum of Floored Pairs?
The optimized solution uses arrays for frequency counting and a prefix sum array for fast range queries. These structures allow constant-time retrieval of how many numbers fall within a numeric interval, which is essential for computing floor division contributions efficiently.
What is the time complexity of Sum of Floored Pairs?
The brute force method runs in O(n^2) time because it evaluates every pair. The optimized approach uses counting and prefix sums with range queries, reducing the complexity to roughly O(M log M), where M is the maximum value in the array. Space complexity is O(M) for the frequency and prefix arrays.