Sum of Floored Pairs — Solution in Python, Java & C++
Sum of Floored Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and math.
Sum of Floored Pairs is a hard coding problem on arrays, math and binary search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Math, Binary Search, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, compute the sum of floor(nums[i] / nums[j]) over all ordered pairs of indices 0 <= i, j < nums.length — including i == j, and counting (i, j) and (j, i) separately.
The sum can be very large; return it modulo 10^9 + 7.
Example 1
Input: nums = [3,7,4]
Output: 7
Explanation: Row by row: 3 → 1+0+0, 7 → 2+1+1, 4 → 1+0+1.
Example 2
Input: nums = [6,6,6]
Output: 9
Explanation: Each of the nine pairs contributes 1.
Example 3
Input: nums = [1,100000]
Output: 100002
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^5
Hints for Sum of Floored Pairs
Hint 1
Fix the divisor
d. Which numerators give a quotient of exactlyk?Hint 2
Those in
[k·d, (k+1)·d - 1]— and a prefix count over values tells you how many there are in O(1).Hint 3
For each distinct divisor
d, loopk = 1, 2, …whilek·d <= max; the total work is a harmonic series, aboutmax · ln(max).
How to solve Sum of Floored Pairs
Group numerators by quotient. For a divisor d, every numerator in [k·d, (k+1)·d - 1] contributes exactly k, and counting the numerators in a value range is a prefix-sum lookup.
Approach
- Let
M = max(nums); buildcnt[v](how many timesvoccurs) and its prefix sumspre[v](how many values are<= v). - For each
dwithcnt[d] > 0, fork = 1, 2, …whilek·d <= M: letc = pre[min(M, (k+1)·d - 1)] - pre[k·d - 1]. - Add
k · c · cnt[d]to the answer (every copy ofdis a separate divisor), reducing modulo 10^9 + 7. - Numerators below
dgive quotient 0 and are never visited.
Why it works
floor(a / d) = k exactly when k·d <= a < (k+1)·d, so the ranges for k = 1, 2, … partition all numerators >= d and each pair (a, d) is counted once with its true quotient. The loop for divisor d runs M / d times, and summing over distinct d gives at most M·(1 + 1/2 + … + 1/M) = O(M log M).
Complexity
- Time —
O(n + M log M) with M = max(nums) - Space —
O(M)
Pitfalls
- The pair count
k · c · cnt[d]can reach 10^15 — use 64-bit arithmetic (or reducek · cfirst in JavaScript). - Remember the duplicates of the divisor: multiply by
cnt[d], and iterate over distinct values only. - The brute-force double loop is O(n²) — 10^10 pairs at the limit.
Reference solution
Python
from typing import List
def sumOfFlooredPairs(nums: List[int]) -> int:
MOD = 10 ** 9 + 7
top = max(nums)
cnt = [0] * (top + 1)
for v in nums:
cnt[v] += 1
pre = [0] * (top + 1)
run = 0
for v in range(top + 1):
run += cnt[v]
pre[v] = run
total = 0
for d in range(1, top + 1):
if cnt[d] == 0:
continue
k = 1
while k * d <= top:
lo = k * d
hi = min(top, lo + d - 1)
total += k * (pre[hi] - pre[lo - 1]) * cnt[d]
k += 1
return total % MODJava
public static int sumOfFlooredPairs(int[] nums) {
final long MOD = 1000000007L;
int top = 0;
for (int v : nums) top = Math.max(top, v);
int[] cnt = new int[top + 1];
for (int v : nums) cnt[v]++;
int[] pre = new int[top + 1];
int run = 0;
for (int v = 0; v <= top; v++) {
run += cnt[v];
pre[v] = run;
}
long total = 0;
for (int d = 1; d <= top; d++) {
if (cnt[d] == 0) continue;
for (int k = 1; (long) k * d <= top; k++) {
int lo = k * d, hi = Math.min(top, lo + d - 1);
long c = pre[hi] - pre[lo - 1];
total = (total + (long) k * c % MOD * cnt[d]) % MOD;
}
}
return (int) total;
}C++
int sumOfFlooredPairs(vector<int>& nums) {
const long long MOD = 1000000007LL;
int top = *max_element(nums.begin(), nums.end());
vector<int> cnt(top + 1, 0), pre(top + 1, 0);
for (int v : nums) cnt[v]++;
int run = 0;
for (int v = 0; v <= top; v++) {
run += cnt[v];
pre[v] = run;
}
long long total = 0;
for (int d = 1; d <= top; d++) {
if (cnt[d] == 0) continue;
for (long long k = 1; k * d <= top; k++) {
int lo = (int) (k * d), hi = min(top, lo + d - 1);
long long c = pre[hi] - pre[lo - 1];
total = (total + k * c % MOD * cnt[d]) % MOD;
}
}
return (int) total;
}JavaScript
var sumOfFlooredPairs = function(nums) {
var MOD = 1000000007;
var top = 0;
for (var i = 0; i < nums.length; i++) if (nums[i] > top) top = nums[i];
var cnt = new Array(top + 1).fill(0);
for (i = 0; i < nums.length; i++) cnt[nums[i]]++;
var pre = new Array(top + 1).fill(0);
var run = 0;
for (var v = 0; v <= top; v++) {
run += cnt[v];
pre[v] = run;
}
var total = 0;
for (var d = 1; d <= top; d++) {
if (cnt[d] === 0) continue;
for (var k = 1; k * d <= top; k++) {
var lo = k * d, hi = Math.min(top, lo + d - 1);
var c = pre[hi] - pre[lo - 1];
if (c > 0) total = (total + ((k * c) % MOD) * cnt[d]) % MOD;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search