Quick Overview

Compute the sum of (i mod j) + (j mod i) over every ordered pair of integers i and j from 1 to n, returned modulo 10^9 + 7, for n up to one million. It tests reasoning about remainders and designing an algorithm far faster than evaluating all n squared pairs.

Sum of Pairwise Modulo Checksums (i mod j + j mod i) for All Pairs up to n

Company: IBM

Role: Business Intelligence Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

A distributed network system has `n` data packets whose identifiers are the integers `1` through `n`. For two identifiers `i` and `j`, the checksum of the pair is ```text C(i, j) = (i mod j) + (j mod i) ``` where `a mod b` is the remainder when `a` is divided by `b` (Python's `a % b`). Compute the sum of `C(i, j)` over every pair with `1 <= i <= n` and `1 <= j <= n`, and return it modulo `10^9 + 7`. ### Function Signature ```python def compute_checksum_aggregation(n: int) -> int: ``` ### Rules - Pairs are ordered: `(i, j)` and `(j, i)` are both counted when `i != j`, and the `n` pairs with `i == j` are included as well (each has checksum 0). - Add up all `n * n` checksums exactly, then return the total modulo `1000000007`, an integer in `[0, 1000000006]`. ### Constraints - `1 <= n <= 10^6` - For the largest inputs the unreduced total is far beyond `2^31 - 1` and also beyond `2^53`; only its remainder modulo `10^9 + 7` is returned. ### Examples **Example 1** ```text Input: n = 2 Output: 2 ``` `C(1, 1) = 0`, `C(1, 2) = 1 + 0 = 1`, `C(2, 1) = 0 + 1 = 1` and `C(2, 2) = 0`, for a total of 2. **Example 2** ```text Input: n = 3 Output: 10 ``` | C(i, j) | j = 1 | j = 2 | j = 3 | | --- | --- | --- | --- | | i = 1 | 0 | 1 | 1 | | i = 2 | 1 | 0 | 3 | | i = 3 | 1 | 3 | 0 | For example, `C(2, 3) = (2 mod 3) + (3 mod 2) = 2 + 1 = 3`. The nine values sum to 10. **Example 3** ```text Input: n = 4 Output: 24 ``` Summing `C(i, j)` over `j = 1, 2, 3, 4` gives 3 for `i = 1`, 6 for `i = 2`, 8 for `i = 3` and 7 for `i = 4`, for a total of 24.

Overview: Compute the sum of (i mod j) + (j mod i) over every ordered pair of integers i and j from 1 to n, returned modulo 10^9 + 7, for n up to one million. It tests reasoning about remainders and designing an algorithm far faster than evaluating all n squared pairs.

Read the full IBM Business Intelligence Engineer interview experience this question came from

A distributed network system has `n` data packets whose identifiers are the integers `1` through `n`. For two identifiers `i` and `j`, the checksum of the pair is ```text C(i, j) = (i mod j) + (j mod i) ``` where `a mod b` is the remainder when `a` is divided by `b` (Python's `a % b`). Implement `compute_checksum_aggregation(n)`, which returns the sum of `C(i, j)` over every pair with `1 <= i <= n` and `1 <= j <= n`, modulo `10^9 + 7`. **Rules** - Pairs are ordered: `(i, j)` and `(j, i)` are both counted when `i != j`, and the `n` pairs with `i == j` are included as well (each has checksum 0). Exactly `n * n` checksums are added. - Add up all `n * n` checksums exactly, then return the total modulo `1000000007`, an integer in `[0, 1000000006]`. **Constraints** - `1 <= n <= 10^6` - For the largest inputs the unreduced total is far beyond `2^31 - 1` and also beyond `2^53` (it always stays below `2^63`); only its remainder modulo `10^9 + 7` is returned, and that remainder fits in a 32-bit signed integer. **Example 1** ```text Input: n = 2 Output: 2 ``` `C(1, 1) = 0`, `C(1, 2) = 1 + 0 = 1`, `C(2, 1) = 0 + 1 = 1` and `C(2, 2) = 0`, for a total of 2. **Example 2** ```text Input: n = 3 Output: 10 ``` | C(i, j) | j = 1 | j = 2 | j = 3 | | --- | --- | --- | --- | | i = 1 | 0 | 1 | 1 | | i = 2 | 1 | 0 | 3 | | i = 3 | 1 | 3 | 0 | For example, `C(2, 3) = (2 mod 3) + (3 mod 2) = 2 + 1 = 3`. The nine values sum to 10.

Constraints

  • 1 <= n <= 10^6
  • For large n the unreduced total exceeds 2^31 - 1 and 2^53 (it stays below 2^63); return it modulo 10^9 + 7 (1000000007), an integer in [0, 1000000006].

Examples

Input: (1,)

Expected Output: 0

Explanation: Minimum n: the only pair is (1, 1) on the diagonal, whose checksum is 0.

Input: (2,)

Expected Output: 2

Explanation: Source example 1: C(1, 2) = C(2, 1) = 1 and both diagonal pairs add 0. Counting only i < j, or only one mod term, would return 1.

Hints

  1. C(i, j) = C(j, i) and the diagonal adds nothing: how does the ordered-pair total relate to adding up only (i mod j) over all ordered pairs?
  2. Visiting all n * n pairs one at a time is too slow for n = 10^6; look for groups of pairs whose remainders can be added in one step.
  3. The total can pass 2^53, so keep it in an exact or 64-bit type, or reduce modulo 10^9 + 7 carefully.

Loading coding console...

Show the approach

Approach

Because C(i, j) = C(j, i) and every diagonal pair contributes 0, the answer is twice S, the sum of (i mod j) over all n * n ordered pairs. Write i mod j = i - j * floor(i / j). Summing i over all ordered pairs gives n * n(n + 1)/2. For a fixed i, the sum over j of j * floor(i / j) adds j once for every multiple j * d <= i, so summing over i = 1..n gives G = sum over all pairs (j, d) with j * d <= n of j * (n + 1 - j * d). Therefore the unreduced total is n^2 (n + 1) - 2G. For a fixed d, j runs over 1..q with q = floor(n / d), contributing (n + 1) * q(q + 1)/2 - d * q(q + 1)(2q + 1)/6. The quotient floor(n / d) takes only O(sqrt(n)) distinct values, and every run of consecutive d from k to h = floor(n / q) that shares the same q is added at once using the run length h - k + 1 and the run sum (k + h)(h - k + 1)/2. Each term is non-negative because d * j <= n, so G only grows. Python integers are exact, so the exact total is reduced modulo 1000000007 only at the end; the Java and C++ references do the same in 64-bit integers (for n <= 10^6 every intermediate stays below 2.1 * 10^18, under 2^63), and the JavaScript reference uses BigInt because the total passes 2^53. Edge cases: n = 1 has only the pair (1, 1) and returns 0; n = 2 returns 2; the modulo first changes the answer once the unreduced total exceeds 1000000007 (for example n = 1400, whose total 1239149884 becomes 239149877).

Time complexity:
O(sqrt(n))
Space complexity:
O(1)