Sum of Floored Pairs

Hard
1312.

Sum of Floored Pairs

Sum of Floored Pairs is a hard coding problem on arrays, math and binary search, asked in Amazon and Google interviews.

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^5
  • 1 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var sumOfFlooredPairs = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= nums[i] <= 10^5

Hints for Sum of Floored Pairs

  1. Hint 1

    Fix the divisor d. Which numerators give a quotient of exactly k?

  2. 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).

  3. Hint 3

    For each distinct divisor d, loop k = 1, 2, … while k·d <= max; the total work is a harmonic series, about max · 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

  1. Let M = max(nums); build cnt[v] (how many times v occurs) and its prefix sums pre[v] (how many values are <= v).
  2. For each d with cnt[d] > 0, for k = 1, 2, … while k·d <= M: let c = pre[min(M, (k+1)·d - 1)] - pre[k·d - 1].
  3. Add k · c · cnt[d] to the answer (every copy of d is a separate divisor), reducing modulo 10^9 + 7.
  4. Numerators below d give 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 reduce k · c first 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 % MOD

Java

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