# Divisible and Non-divisible Sums Difference
**Difficulty:** EASY
[External](https://leetcode.com/problems/divisible-and-non-divisible-sums-difference)
Canonical: https://scaleengineer.com/dsa/problems/divisible-and-non-divisible-sums-difference
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
You are given positive integers `n` and `m`.

Define two integers as follows:

* `num1`: The sum of all integers in the range `[1, n]` (both **inclusive**) that are **not divisible** by `m`.
* `num2`: The sum of all integers in the range `[1, n]` (both **inclusive**) that are **divisible** by `m`.

Return _the integer_ `num1 - num2`.

**Example 1:**

**Input:** n = 10, m = 3
**Output:** 19
**Explanation:** In the given example:
- Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.
- Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18.
We return 37 - 18 = 19 as the answer.

**Example 2:**

**Input:** n = 5, m = 6
**Output:** 15
**Explanation:** In the given example:
- Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.
- Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0.
We return 15 - 0 = 15 as the answer.

**Example 3:**

**Input:** n = 5, m = 1
**Output:** -15
**Explanation:** In the given example:
- Integers in the range [1, 5] that are not divisible by 1 are [], num1 is the sum of those integers = 0.
- Integers in the range [1, 5] that are divisible by 1 are [1,2,3,4,5], num2 is the sum of those integers = 15.
We return 0 - 15 = -15 as the answer.

**Constraints:**

* `1 <= n, m <= 1000`

# Approaches
## Brute-Force Iteration
This approach directly follows the problem description by iterating through all numbers from 1 to `n`. It maintains two separate sums: one for numbers divisible by `m` (`num2`) and one for numbers not divisible by `m` (`num1`). For each number, it determines which category it falls into and updates the corresponding sum. Finally, it calculates and returns the difference `num1 - num2`.
**Time:** O(n) - The algorithm iterates through `n` numbers once. The operations inside the loop (modulo, addition) take constant time. Therefore, the total time complexity is linear with respect to `n`. · **Space:** O(1) - The memory usage is constant as it only requires a few variables to store the sums and the loop counter, regardless of the input size `n`.
**Pros:** Very simple to understand and implement.; It's a direct translation of the problem statement into code, making it easy to verify its correctness.
**Cons:** Less efficient for very large values of `n` compared to the mathematical approach.; Performs `n` iterations, which can be slow if `n` is extremely large (though acceptable for the given constraints).
### Explanation
The most straightforward way to solve this problem is to simulate the process described. We can use a loop that runs from 1 to `n`. In each iteration, we check if the current number `i` is divisible by `m`. We use two variables, `num1` and `num2`, initialized to zero, to accumulate the sums. If `i % m` is 0, we add `i` to `num2`; otherwise, we add it to `num1`. After the loop has processed all numbers up to `n`, the final answer is simply `num1 - num2`.

```java
class Solution {
    public int differenceOfSums(int n, int m) {
        int num1 = 0; // Sum of integers not divisible by m
        int num2 = 0; // Sum of integers divisible by m

        for (int i = 1; i <= n; i++) {
            if (i % m == 0) {
                num2 += i;
            } else {
                num1 += i;
            }
        }

        return num1 - num2;
    }
}
```
### Algorithm
- Initialize two integer variables, `num1` and `num2`, to 0.
- Loop through each integer `i` from 1 to `n`.
- Inside the loop, check if `i` is divisible by `m` using the modulo operator (`i % m == 0`).
- If `i` is divisible by `m`, add `i` to `num2`.
- Otherwise, add `i` to `num1`.
- After the loop finishes, return the result of `num1 - num2`.

## Mathematical Formula (Arithmetic Progression)
A more efficient, constant-time approach can be derived using mathematical properties of arithmetic series. Instead of iterating, we can calculate the required sums directly. The key insight is that `num1 - num2` can be rewritten as `(sum of all numbers from 1 to n) - 2 * (sum of numbers divisible by m)`. Both of these sums can be calculated using well-known formulas for arithmetic progressions.
**Time:** O(1) - The result is computed using a few arithmetic operations, regardless of the values of `n` and `m`. This is the most optimal time complexity possible. · **Space:** O(1) - The solution uses a fixed number of variables for calculations, so its memory usage is constant and does not depend on the input size.
**Pros:** Extremely efficient, with a constant time complexity.; Scales perfectly even for very large values of `n` and `m`.
**Cons:** Requires some mathematical insight to derive the formula.; Might be slightly less intuitive at first glance compared to the direct simulation.
### Explanation
This optimized approach avoids iteration by using mathematical formulas. 
First, we observe the relationship between `num1`, `num2`, and the total sum of numbers from 1 to `n` (`totalSum`). By definition, `totalSum = num1 + num2`. The value we need to compute is `num1 - num2`. By substituting `num1 = totalSum - num2`, we get `(totalSum - num2) - num2`, which simplifies to `totalSum - 2 * num2`.

Now, the problem is reduced to calculating `totalSum` and `num2` efficiently.
1.  **`totalSum`**: The sum of the first `n` integers is given by the formula `n * (n + 1) / 2`.
2.  **`num2`**: This is the sum of all multiples of `m` up to `n` (i.e., `m, 2m, 3m, ..., k*m` where `k*m <= n`). We can factor out `m` to get `m * (1 + 2 + 3 + ... + k)`. The number of terms, `k`, is `n / m` (integer division). The sum `1 + 2 + ... + k` is `k * (k + 1) / 2`. Therefore, `num2 = m * (k * (k + 1) / 2)`.

By calculating these two values and plugging them into `totalSum - 2 * num2`, we get the answer in constant time.

```java
class Solution {
    public int differenceOfSums(int n, int m) {
        // Sum of all numbers from 1 to n
        int totalSum = n * (n + 1) / 2;

        // Count of numbers divisible by m
        int k = n / m;

        // Sum of numbers divisible by m is m * (1 + 2 + ... + k)
        int sumDivisible = m * (k * (k + 1) / 2);

        // We need num1 - num2.
        // num1 = totalSum - sumDivisible
        // num2 = sumDivisible
        // So, num1 - num2 = (totalSum - sumDivisible) - sumDivisible
        // = totalSum - 2 * sumDivisible
        return totalSum - 2 * sumDivisible;
    }
}
```
### Algorithm
- Let `totalSum` be the sum of all integers from 1 to `n`.
- We know `totalSum = num1 + num2`.
- The expression to find is `num1 - num2`.
- Substitute `num1 = totalSum - num2` into the expression: `(totalSum - num2) - num2 = totalSum - 2 * num2`.
- Calculate `totalSum` using the arithmetic series formula: `n * (n + 1) / 2`.
- Calculate `num2` (sum of numbers divisible by `m`).
  - The number of terms divisible by `m` is `k = n / m`.
  - The sum of these terms is `m * (1 + 2 + ... + k)`, which is `m * k * (k + 1) / 2`.
- Return the final result: `totalSum - 2 * num2`.

# Solutions
### Java

```java
class Solution {
public
  int differenceOfSums(int n, int m) {
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans += i % m == 0 ? -i : i;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int differenceOfSums(int n, int m) {
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans += i % m ? i : -i;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def differenceOfSums(self, n: int, m: int) -> int: return sum(i if i %
                                                                  m else - i for i in range(1, n + 1))

```