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

1
2
3
4
5
6
7
8
9

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

1
2

Input: nums = [7,7,7,7,7,7,7]
Output: 49

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= 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

  1. Find the maximum value in the array (max_num).
  2. Count the frequency of each number in nums.
  3. Build a prefix sum array of frequencies.
  4. For each possible divisor d from 1 to max_num, for each multiple of d, count how many numbers fall into that range and add count * freq[d] * k to the answer, where k is the floored value.
  5. Return the answer modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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) where n is the length of nums and m is the maximum value in nums. We count frequencies and build prefix sums in O(m), and for each divisor, the inner loop runs about O(log m) times, so total is O(m log m).
  • 🧺 Space complexity: O(m) for the frequency and prefix sum arrays, where m is the maximum value in nums.