Sum of floored pairs

Array Math Binary Search Counting Enumeration Prefix Sum

30.7% acceptance

Feb 25, 2026

466

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. Return it modulo 10^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_of_floored_pairs(nums: Vec<i32>) -> i32 {
    const MOD: u64 = 1_000_000_007;
    let max_val = *nums.iter().max().unwrap() as usize;

    let mut cnt = vec![0u64; max_val + 1];
    for &x in &nums {
      cnt[x as usize] += 1;
    }

    // prefix[v] = number of elements <= v
    let mut prefix = vec![0u64; max_val + 2];
    for v in 1..=max_val {
      prefix[v] = prefix[v - 1] + cnt[v];
    }

    let mut ans: u64 = 0;
    for d in 1..=max_val {
      if cnt[d] == 0 { continue; }
      let mut k = 1usize;
      loop {
        let lo = k * d;
        if lo > max_val { break; }
        let hi = ((k + 1) * d - 1).min(max_val);
        let count_in_range = prefix[hi] - prefix[lo - 1];
        ans = (ans + (k as u64 % MOD) * (count_in_range % MOD) % MOD * (cnt[d] % MOD)) % MOD;
        k += 1;
      }
    }

    ans as i32
  }
}