2894. Divisible and Non-Divisible Sums Difference

2894. Divisible and Non-Divisible Sums Difference

Thought

Problem statement: In $[1, n]$, find the difference between the sum of all numbers not divisible by $m$ and the sum of all numbers divisible by $m$.

Derivation:

1. Total sum: $S_{\text{total}} = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

2. Numbers divisible by $m$ are: $m, 2m, 3m, \dots, \left\lfloor \frac{n}{m} \right\rfloor m$ $S_{\text{divisible}} = m \cdot \left(1 + 2 + \dots + k\right) = m \cdot \frac{k(k+1)}{2}$

3. Therefore the sum of non-divisible numbers is: $S_{\text{not\_div}} = S_{\text{total}} - S_{\text{divisible}}$

4. The answer is: $\text{difference} = S_{\text{not\_div}} - S_{\text{divisible}}$ $= \frac{n(n+1)}{2} - m \cdot \frac{\left\lfloor \frac{n}{m} \right\rfloor(\left\lfloor \frac{n}{m} \right\rfloor+1)}{2} - m \cdot \frac{\left\lfloor \frac{n}{m} \right\rfloor(\left\lfloor \frac{n}{m} \right\rfloor+1)}{2}$ $= \frac{n(n+1)}{2} - m \cdot \left\lfloor \frac{n}{m} \right\rfloor(\left\lfloor \frac{n}{m} \right\rfloor+1)$

Code

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # divisible = m * (1 + n // m) * (n // m) // 2
        # undivisible = n * (n + 1) // 2 - n * ((1 + n // m) * (n // m) // 2)
        return - m * ((1 + n // m) * (n // m)) + (n * (n + 1) >> 1)

const differenceOfSums = (n: number, m: number): number =>
  -m * ((1 + Math.floor(n / m)) * Math.floor(n / m)) + ((n * (n + 1)) >> 1);

Involution Hell© 2026 byCommunityunderCC BY-NC-SA 4.0