Sum of Floored Pairs

Given an integer array nums, return the sum of floor(nums[i] / nums[j]) for all pairs (i, j) where 0 <= i, j < len(nums). Since the answer can be large, return it modulo 10^9 + 7.

This is LeetCode 1862: Sum of Floored Pairs, and it is a hard problem that looks deceptively simple. The brute force is obvious but way too slow. The efficient solution leans on frequency counting, prefix sums, and the harmonic series, a combination that transforms an O(n^2) nightmare into something much more manageable.

Why this problem matters

Sum of Floored Pairs forces you to think about batch computation. Instead of evaluating each pair individually, you group values by their frequency and use range queries to count contributions in bulk. That shift from "enumerate all pairs" to "count how many pairs produce the same quotient" is a powerful mental model that shows up in number theory problems, counting problems, and optimization problems alike.

The harmonic series insight is the real gem here. When you iterate over multiples of each value d, the total number of iterations across all values is bounded by max_val * (1 + 1/2 + 1/3 + ... + 1/max_val), which is O(max_val * log(max_val)). That sum grows slowly enough to keep the solution efficient even when the array contains large values.

The approach

The brute force computes floor(nums[i] / nums[j]) for every pair, which takes O(n^2) time. With n up to 100,000 and values up to 100,000, that is 10 billion operations. Not going to work.

The key observation: floor(v / d) = k for all values v in the range [k*d, (k+1)*d - 1]. So instead of iterating over every pair, you can:

1. Build a frequency array count[v] that records how many times each value appears in nums.
2. Build a prefix sum over the frequency array so you can quickly query "how many elements fall in the range [lo, hi]?"
3. For each distinct value d in nums, iterate over multiples k = 1, 2, 3, ... and use the prefix sum to find how many elements have a quotient of exactly k when divided by d. Multiply by k and by count[d], and add it to the answer.

The iteration over multiples of d costs O(max_val / d) for each d. Summing this across all values of d gives the harmonic series bound.

The solution

def sumOfFlooredPairs(nums):
    MOD = 10**9 + 7
    max_val = max(nums)

    count = [0] * (max_val + 1)
    for v in nums:
        count[v] += 1

    prefix = [0] * (max_val + 2)
    for i in range(1, max_val + 1):
        prefix[i] = prefix[i - 1] + count[i]

    result = 0
    for d in range(1, max_val + 1):
        if count[d] == 0:
            continue
        for k in range(1, max_val // d + 1):
            lo = k * d
            hi = min((k + 1) * d - 1, max_val)
            elements_in_range = prefix[hi] - prefix[lo - 1]
            result = (result + count[d] * k * elements_in_range) % MOD

    return result

The outer loop runs over every value from 1 to max_val. The inner loop runs over multiples of d. The prefix sum query answers "how many elements of nums fall in this range?" in O(1). That is the entire algorithm.

Step-by-step walkthrough

The walkthrough shows nums = [2, 5, 9] with max_val = 9. For each distinct denominator d, you sweep through ranges of size d, query the prefix sum, and accumulate weighted counts. The grand total of 10 matches what you get from brute-forcing all 9 pairs.

Complexity analysis

Here M = max(nums). The O(M * log(M)) comes from the harmonic series: summing max_val/1 + max_val/2 + ... + max_val/max_val = max_val * H(max_val), where H is the harmonic number, which grows as O(log(M)). The space is O(M) for the count and prefix arrays.

The building blocks

Frequency counting + prefix sum + harmonic iteration

This problem combines three techniques into one clean solution:

• Frequency array: counting occurrences of each value so you can process distinct values rather than individual elements
• Prefix sum on the frequency array: enabling O(1) range queries for "how many elements fall in [lo, hi]?"
• Harmonic series iteration: sweeping through multiples of each value d, which gives a total cost of O(M * log(M)) across all values

The same harmonic iteration idea shows up whenever you need to process divisors or multiples efficiently. The Sieve of Eratosthenes uses a similar pattern (marking multiples of each prime), and so do problems that involve counting divisor pairs or computing GCD-related sums.

Edge cases

• All elements identical. If every element is the same value v, then floor(v / v) = 1 for all n^2 pairs. The answer is n^2 mod (10^9 + 7). The algorithm handles this because count[v] = n and the only contributing range is [v, 2v-1] with k=1.
• Array contains 1. When d = 1, the inner loop runs from k = 1 to max_val, contributing every element's value to the sum. This is the most expensive single denominator, but it is still bounded by O(max_val) iterations.
• Single element. With n = 1, there is exactly one pair (0, 0), and the answer is floor(nums[0] / nums[0]) = 1. The algorithm naturally returns 1.
• Large values. When max_val is close to 100,000, the harmonic sum is roughly 100,000 * 12 (since ln(100,000) is about 11.5). That is around 1.2 million iterations total, well within time limits.
• Modular arithmetic. The answer can exceed 10^9 + 7, so you must take the modulo at each accumulation step. Missing this causes wrong answers on large inputs.

From understanding to recall

The hardest part of this problem is not the code itself. It is remembering the three-part structure: frequency array, prefix sum, harmonic iteration over multiples. Each piece is simple in isolation, but assembling them under time pressure requires practice.

Spaced repetition helps you internalize the pattern. After a few review sessions where you reconstruct the solution from scratch, the connection between "floor division over pairs" and "prefix sum over multiples" becomes automatic. You stop thinking about which loop goes where and start thinking about why it works.

Related posts

• Subarray Sum Equals K - Another problem where prefix sums transform a quadratic enumeration into a linear scan
• Product of Array Except Self - Uses the same idea of precomputing cumulative information to avoid redundant pair-wise computation
• Count Primes - The Sieve of Eratosthenes uses the same harmonic series iteration pattern, marking multiples of each prime

CodeBricks uses spaced repetition to help you internalize patterns like frequency counting and prefix sums. Instead of re-reading solutions, you practice reconstructing them from memory at increasing intervals. Each review strengthens the link between "pair enumeration problem" and "harmonic series optimization."