Sum of Floored Pairs
HardUpdated: Aug 2, 2025
Practice on:
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 10^9 + 7.
The floor() function returns the integer part of the division.
Examples
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 <= 10^51 <= nums[i] <= 10^5
Solution
Method 1 – Prefix Sum and Counting (Optimal)
Intuition
The key idea is to count, for each possible divisor, how many numbers in the array are divisible by it, and use prefix sums to efficiently compute the sum of floored pairs. Instead of brute-forcing all pairs, we use counting and prefix sums to reduce the time complexity.
Approach
- Find the maximum value in the array (
max_num). - Count the frequency of each number in
nums. - Build a prefix sum array of frequencies.
- For each possible divisor
dfrom 1 tomax_num, for each multiple ofd, count how many numbers fall into that range and addcount * freq[d] * kto the answer, wherekis the floored value. - Return the answer modulo
10^9 + 7.
Code
C++
class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
int mod = 1e9 + 7;
int max_num = *max_element(nums.begin(), nums.end());
vector<int> freq(max_num + 2, 0);
for (int n : nums) freq[n]++;
vector<int> prefix(max_num + 2, 0);
for (int i = 1; i <= max_num + 1; ++i) prefix[i] = prefix[i-1] + freq[i];
int ans = 0;
for (int d = 1; d <= max_num; ++d) {
if (freq[d] == 0) continue;
for (int k = 1; d * k <= max_num; ++k) {
int l = d * k, r = min(d * (k + 1) - 1, max_num);
int cnt = prefix[r] - prefix[l - 1];
ans = (ans + 1LL * freq[d] * cnt * k) % mod;
}
}
return ans;
}
};
Go
func sumOfFlooredPairs(nums []int) int {
mod := int(1e9 + 7)
maxNum := 0
for _, n := range nums {
if n > maxNum {
maxNum = n
}
}
freq := make([]int, maxNum+2)
for _, n := range nums {
freq[n]++
}
prefix := make([]int, maxNum+2)
for i := 1; i <= maxNum+1; i++ {
prefix[i] = prefix[i-1] + freq[i]
}
ans := 0
for d := 1; d <= maxNum; d++ {
if freq[d] == 0 {
continue
}
for k := 1; d*k <= maxNum; k++ {
l := d * k
r := d*(k+1) - 1
if r > maxNum {
r = maxNum
}
cnt := prefix[r] - prefix[l-1]
ans = (ans + freq[d]*cnt*k) % mod
}
}
return ans
}
Java
class Solution {
public int sumOfFlooredPairs(int[] nums) {
int mod = 1_000_000_007;
int maxNum = 0;
for (int n : nums) maxNum = Math.max(maxNum, n);
int[] freq = new int[maxNum + 2];
for (int n : nums) freq[n]++;
int[] prefix = new int[maxNum + 2];
for (int i = 1; i <= maxNum + 1; i++) prefix[i] = prefix[i-1] + freq[i];
long ans = 0;
for (int d = 1; d <= maxNum; d++) {
if (freq[d] == 0) continue;
for (int k = 1; d * k <= maxNum; k++) {
int l = d * k, r = Math.min(d * (k + 1) - 1, maxNum);
int cnt = prefix[r] - prefix[l - 1];
ans = (ans + 1L * freq[d] * cnt * k) % mod;
}
}
return (int) ans;
}
}
Kotlin
class Solution {
fun sumOfFlooredPairs(nums: IntArray): Int {
val mod = 1_000_000_007
val maxNum = nums.maxOrNull() ?: 0
val freq = IntArray(maxNum + 2)
for (n in nums) freq[n]++
val prefix = IntArray(maxNum + 2)
for (i in 1..maxNum+1) prefix[i] = prefix[i-1] + freq[i]
var ans = 0L
for (d in 1..maxNum) {
if (freq[d] == 0) continue
var k = 1
while (d * k <= maxNum) {
val l = d * k
val r = minOf(d * (k + 1) - 1, maxNum)
val cnt = prefix[r] - prefix[l - 1]
ans = (ans + freq[d].toLong() * cnt * k) % mod
k++
}
}
return ans.toInt()
}
}
Python
class Solution:
def sumOfFlooredPairs(self, nums: list[int]) -> int:
mod = 10 ** 9 + 7
max_num = max(nums)
freq = [0] * (max_num + 2)
for n in nums:
freq[n] += 1
prefix = [0] * (max_num + 2)
for i in range(1, max_num + 2):
prefix[i] = prefix[i-1] + freq[i]
ans = 0
for d in range(1, max_num + 1):
if freq[d] == 0:
continue
k = 1
while d * k <= max_num:
l = d * k
r = min(d * (k + 1) - 1, max_num)
cnt = prefix[r] - prefix[l - 1]
ans = (ans + freq[d] * cnt * k) % mod
k += 1
return ans
Rust
impl Solution {
pub fn sum_of_floored_pairs(nums: Vec<i32>) -> i32 {
let m = *nums.iter().max().unwrap() as usize;
let mut freq = vec![0; m + 2];
for &n in &nums {
freq[n as usize] += 1;
}
let mut prefix = vec![0; m + 2];
for i in 1..=m+1 {
prefix[i] = prefix[i-1] + freq[i];
}
let mut ans = 0i64;
let modulo = 1_000_000_007i64;
for d in 1..=m {
if freq[d] == 0 { continue; }
let mut k = 1;
while d * k <= m {
let l = d * k;
let r = (d * (k + 1) - 1).min(m);
let cnt = prefix[r] - prefix[l - 1];
ans = (ans + freq[d] as i64 * cnt as i64 * k as i64) % modulo;
k += 1;
}
}
ans as i32
}
}
TypeScript
class Solution {
sumOfFlooredPairs(nums: number[]): number {
const mod = 1e9 + 7;
const maxNum = Math.max(...nums);
const freq = new Array(maxNum + 2).fill(0);
for (const n of nums) freq[n]++;
const prefix = new Array(maxNum + 2).fill(0);
for (let i = 1; i <= maxNum + 1; i++) prefix[i] = prefix[i-1] + freq[i];
let ans = 0;
for (let d = 1; d <= maxNum; d++) {
if (freq[d] === 0) continue;
for (let k = 1; d * k <= maxNum; k++) {
const l = d * k;
const r = Math.min(d * (k + 1) - 1, maxNum);
const cnt = prefix[r] - prefix[l - 1];
ans = (ans + freq[d] * cnt * k) % mod;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n + m log m)wherenis the length ofnumsandmis the maximum value innums. We count frequencies and build prefix sums inO(m), and for each divisor, the inner loop runs aboutO(log m)times, so total isO(m log m). - 🧺 Space complexity:
O(m)for the frequency and prefix sum arrays, wheremis the maximum value innums.