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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3
4
5
6

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

Solution

Method 1 - Using Maths

We need to calculate two sums:

  • num1: The sum of integers from 1 to n that are not divisible by m.
  • num2: The sum of integers from 1 to n that are divisible by m. Finally, return the value of num1 - num2.

We can use the formula for the sum of an arithmetic series to compute the total sums efficiently.

  • Sum of the first k natural numbers is $\text{Sum} = \frac{k \times (k + 1)}{2}$.
  • For num2, the sum of integers divisible by m can be expressed as the sum of a sequence $m, 2m, 3m, \ldots, km$, where $k = \lfloor \frac{n}{m} \rfloor$.
    • Formula: $\text{Sum} = m \times \frac{k \times (k + 1)}{2}$.

Here are the steps we can take:

  • Compute the total sum of integers ( [1, n] ).
  • Compute num2 (sum of integers divisible by m using the sequence formula).
  • Calculate num1 (subtract num2 from the total sum).
  • Return num1 - num2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int differenceOfSums(int n, int m) {
        // Total sum of numbers from 1 to n
        int totalSum = (n * (n + 1)) / 2;
        
        // Sum of numbers divisible by m
        int k = n / m;
        int divSum = m * (k * (k + 1)) / 2;
        
        // num1 - num2
        int ans = totalSum - 2 * divSum;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # Total sum of numbers from 1 to n
        total_sum = (n * (n + 1)) // 2
        
        # Sum of numbers divisible by m
        k = n // m
        div_sum = m * (k * (k + 1)) // 2
        
        # num1 - num2
        ans = total_sum - 2 * div_sum
        return ans

Complexity

  • ⏰ Time complexity: O(1) as computing total sum, divisible sum, and handling basic arithmetic - are all O(1) operations.
  • 🧺 Space complexity: O(1) as no additional space other than variables.