Difficulty: 🟢 Easy
Topics: Math

Solution

LeetCode 2894 - Divisible and Non-divisible Sums Difference

Problem Understanding

This problem gives us two positive integers, n and m. We need to examine every integer in the inclusive range [1, n] and separate the numbers into two groups based on divisibility by m.

The first group contains all numbers that are not divisible by m. The sum of these numbers is called num1.

The second group contains all numbers that are divisible by m. The sum of these numbers is called num2.

Our goal is to return the value:

$$num1 - num2$$

In other words, we add all non-divisible numbers together, add all divisible numbers together, and then subtract the second sum from the first.

For example, when n = 10 and m = 3, the numbers divisible by 3 are 3, 6, and 9, whose sum is 18. The remaining numbers sum to 37. The final answer is 37 - 18 = 19.

The constraints are:

1 <= n <= 1000
1 <= m <= 1000

These constraints are very small. Even a straightforward iteration through all numbers from 1 to n is easily fast enough. However, there is also a mathematical observation that allows us to compute the answer in constant time.

Several edge cases are worth considering. If m > n, then no number in the range is divisible by m, so num2 becomes 0. If m = 1, then every number is divisible by m, so num1 becomes 0. We must also correctly handle the smallest possible input, such as n = 1.

Approaches

Brute Force Approach

The most direct solution is to iterate through every integer from 1 to n.

For each number:

If it is divisible by m, add it to num2.
Otherwise, add it to num1.

After processing all numbers, return num1 - num2.

This approach is correct because every number in the range belongs to exactly one of the two groups. By accumulating the sums separately, we obtain the required result directly.

Although this approach is already efficient enough for n <= 1000, it still performs a loop over all numbers.

Optimal Mathematical Approach

The key observation is that all numbers from 1 to n contribute to either num1 or num2.

Let:

$$total = 1 + 2 + \dots + n$$

Using the arithmetic series formula:

$$total = \frac{n(n+1)}{2}$$

Next, determine the sum of all multiples of m in the range [1, n].

The number of multiples is:

$$k = \left\lfloor \frac{n}{m} \right\rfloor$$

These multiples are:

$$m, 2m, 3m, \dots, km$$

Their sum is:

$$num2 = m(1+2+\dots+k)$$

Using the arithmetic series formula again:

$$num2 = m \cdot \frac{k(k+1)}{2}$$

Since:

$$num1 = total - num2$$

the required answer becomes:

$$num1 - num2 = (total - num2) - num2 = total - 2 \cdot num2$$

This allows us to compute the result in constant time without iterating through the range.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through every number and classify by divisibility
Optimal	O(1)	O(1)	Use arithmetic progression formulas

Algorithm Walkthrough

Optimal Algorithm

Compute the sum of all integers from 1 to n using the arithmetic series formula.
Compute k = n // m, which represents how many multiples of m exist in the range.
Compute the sum of those multiples using the arithmetic progression formula m * k * (k + 1) // 2.
Store this value as divisible_sum.
Since all remaining numbers are non-divisible, their sum is total_sum - divisible_sum.
Return (total_sum - divisible_sum) - divisible_sum.
Simplify the computation as total_sum - 2 * divisible_sum.

Why it works

Every integer from 1 to n belongs to exactly one of two groups: divisible by m or not divisible by m. Therefore:

$$total_sum = num1 + num2$$

Rearranging gives:

$$num1 = total_sum - num2$$

Substituting into the required expression:

$$num1 - num2 = (total_sum - num2) - num2 = total_sum - 2 \cdot num2$$

Since the arithmetic progression formula correctly computes both the total sum and the sum of all multiples of m, the algorithm always produces the correct result.

Python Solution

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

        count_multiples = n // m
        divisible_sum = m * count_multiples * (count_multiples + 1) // 2

        return total_sum - 2 * divisible_sum

The implementation begins by computing the sum of all integers from 1 to n. It then determines how many multiples of m appear within the range by using integer division.

Once the count of multiples is known, the arithmetic progression formula computes the sum of all divisible numbers directly. Finally, the formula total_sum - 2 * divisible_sum returns the required difference.

No loops or auxiliary data structures are required.

Go Solution

func differenceOfSums(n int, m int) int {
	totalSum := n * (n + 1) / 2

	countMultiples := n / m
	divisibleSum := m * countMultiples * (countMultiples + 1) / 2

	return totalSum - 2*divisibleSum
}

The Go implementation follows exactly the same mathematical derivation as the Python version.

Since the constraints are at most 1000, integer overflow is not a concern. All computations comfortably fit within Go's standard int type. No slices, maps, or additional memory allocations are needed.

Worked Examples

Example 1

Input:

n = 10
m = 3

Compute the total sum:

Value	Result
total_sum	10 × 11 ÷ 2 = 55

Compute multiples of 3:

Value	Result
count_multiples	10 ÷ 3 = 3
multiples	3, 6, 9
divisible_sum	3 × 4 ÷ 2 × 3 = 18

Compute answer:

Expression	Result
total_sum - 2 × divisible_sum	55 - 36
Answer	19

Example 2

Input:

n = 5
m = 6

Compute the total sum:

Value	Result
total_sum	5 × 6 ÷ 2 = 15

Compute multiples:

Value	Result
count_multiples	5 ÷ 6 = 0
divisible_sum	0

Compute answer:

Expression	Result
total_sum - 2 × divisible_sum	15 - 0
Answer	15

Example 3

Input:

n = 5
m = 1

Compute the total sum:

Value	Result
total_sum	15

Compute multiples:

Value	Result
count_multiples	5
divisible_sum	1 + 2 + 3 + 4 + 5 = 15

Compute answer:

Expression	Result
total_sum - 2 × divisible_sum	15 - 30
Answer	-15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Uses a fixed number of arithmetic operations
Space	O(1)	Only a few variables are stored

The solution relies entirely on mathematical formulas. Regardless of the values of n and m, the same number of calculations is performed. Therefore both time and space complexity remain constant.

Test Cases

sol = Solution()

assert sol.differenceOfSums(10, 3) == 19      # Example 1
assert sol.differenceOfSums(5, 6) == 15       # Example 2, no divisible numbers
assert sol.differenceOfSums(5, 1) == -15      # Example 3, all numbers divisible

assert sol.differenceOfSums(1, 1) == -1       # Smallest input
assert sol.differenceOfSums(1, 2) == 1        # m larger than n

assert sol.differenceOfSums(2, 2) == -1       # Single divisible number
assert sol.differenceOfSums(3, 2) == 2        # Mixed divisible and non-divisible

assert sol.differenceOfSums(1000, 1000) == (
    1000 * 1001 // 2 - 2 * 1000
)                                               # Largest equal values

assert sol.differenceOfSums(1000, 1) == -500500 # Every number divisible

assert sol.differenceOfSums(7, 10) == 28        # No multiples present

Test Summary

Test	Why
`(10, 3)`	Validates the primary example
`(5, 6)`	Checks when no numbers are divisible
`(5, 1)`	Checks when every number is divisible
`(1, 1)`	Smallest valid input
`(1, 2)`	`m` greater than `n`
`(2, 2)`	Exactly one divisible number
`(3, 2)`	Typical mixed case
`(1000, 1000)`	Largest equal values
`(1000, 1)`	Maximum range with all numbers divisible
`(7, 10)`	No divisible numbers in range

Edge Cases

When `m` Is Greater Than `n`

If m > n, there are no multiples of m in the range [1, n]. A common mistake is assuming at least one divisible number exists. In this situation, n // m correctly evaluates to 0, causing divisible_sum to become 0. The algorithm therefore returns the sum of all numbers from 1 to n, which is correct.

When `m = 1`

Every positive integer is divisible by 1. Therefore, the non-divisible set is empty and num1 = 0. Some implementations incorrectly assume both groups contain elements. Here, n // 1 = n, so the formula computes the sum of every number in the range as divisible_sum, leading to the correct result 0 - total_sum.

Minimum Input Size

When n = 1, there is only a single number to consider. Small inputs often expose off-by-one errors in arithmetic progression formulas. The formulas used here remain valid because they naturally evaluate to the correct sums even when only one element exists.

Exactly One Multiple of `m`

Cases such as n = 2 and m = 2 contain exactly one divisible number. Some implementations mishandle boundary conditions when counting multiples. The expression n // m correctly returns 1, ensuring the arithmetic progression formula computes the divisible sum accurately.

LeetCode 2894 - Divisible and Non-divisible Sums Difference

Solution

LeetCode 2894 - Divisible and Non-divisible Sums Difference

Problem Understanding

Approaches

Brute Force Approach

Optimal Mathematical Approach

Approach Comparison

Algorithm Walkthrough

Optimal Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Example 3

Complexity Analysis

Test Cases

Test Summary

Edge Cases

When m Is Greater Than n

When m = 1

Minimum Input Size

Exactly One Multiple of m

When `m` Is Greater Than `n`

When `m = 1`

Exactly One Multiple of `m`