Divisible and Non-divisible Sums Difference

Easy

#2575Time: 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`.

Patterns

Math

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int differenceOfSums(int n, int m) {3        int num1 = 0; // Sum of integers not divisible by m4        int num2 = 0; // Sum of integers divisible by m5 6        for (int i = 1; i <= n; i++) {7            if (i % m == 0) {8                num2 += i;9            } else {10                num1 += i;11            }12        }13 14        return num1 - num2;15    }16}

Complexity

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`.

Trade-offs

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

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.

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.

Walkthrough

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.

totalSum: The sum of the first n integers is given by the formula n * (n + 1) / 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.

1class Solution {2    public int differenceOfSums(int n, int m) {3        // Sum of all numbers from 1 to n4        int totalSum = n * (n + 1) / 2;5 6        // Count of numbers divisible by m7        int k = n / m;8 9        // Sum of numbers divisible by m is m * (1 + 2 + ... + k)10        int sumDivisible = m * (k * (k + 1) / 2);11 12        // We need num1 - num2.13        // num1 = totalSum - sumDivisible14        // num2 = sumDivisible15        // So, num1 - num2 = (totalSum - sumDivisible) - sumDivisible16        // = totalSum - 2 * sumDivisible17        return totalSum - 2 * sumDivisible;18    }19}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int differenceOfSums(int n, int m) {4    int ans = 0;5    for (int i = 1; i <= n; ++i) {6      ans += i % m == 0 ? -i : i;7    }8    return ans;9  }10}

1class Solution {2public:3  int differenceOfSums(int n, int m) {4    int ans = 0;5    for (int i = 1; i <= n; ++i) {6      ans += i % m ? i : -i;7    }8    return ans;9  }10};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem