#2894

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Divisible and Non-divisible Sums Difference

Compute the difference between sums of integers divisible and non-divisible by m using a direct arithmetic approach efficiently.

math

Problem Statement

Given two positive integers n and m, calculate two sums: one for integers in the range 1 to n that are divisible by m, and another for integers that are not divisible by m.

Return the difference between the sum of non-divisible integers and the sum of divisible integers. Ensure your solution handles the full range efficiently using math-driven reasoning without explicit loops.

Examples

Example 1

Input: n = 10, m = 3

Output: 19

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

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

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 Approach

Sum All Integers Using Formula

Compute the total sum of integers from 1 to n using the formula n * (n + 1) / 2. This captures all integers efficiently in O(1) time.

Sum Divisible Integers

Find the largest multiple of m within n. Compute the sum of divisible integers using m * k * (k + 1) / 2 where k is the count of multiples, leveraging arithmetic progression.

Subtract Divisible from Total

Calculate the sum of non-divisible integers by subtracting the divisible sum from the total sum, then return this difference as the final result.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

Time complexity is O(1) because all sums are computed using closed formulas. Space complexity is O(1) as only a few integer variables are needed.

What Interviewers Usually Probe

Ask candidate to derive sums without iteration, hinting at arithmetic progression usage.
Check if the candidate correctly identifies divisible and non-divisible sets and computes sums separately.
Watch for off-by-one mistakes when calculating the number of multiples of m.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include n when computing sums can cause off-by-one errors.
Using loops instead of formulas reduces efficiency and fails the O(1) expectation.
Confusing sum of divisible and non-divisible integers, leading to incorrect subtraction order.

Follow-up variants

Compute the difference for a list of multiple m values simultaneously.
Return the ratio instead of difference between divisible and non-divisible sums.
Handle large n and m using modular arithmetic to avoid overflow.

FAQ

What formula should I use to sum integers from 1 to n?

Use the arithmetic progression formula sum = n * (n + 1) / 2 for all integers from 1 to n.

How do I calculate the sum of integers divisible by m efficiently?

Compute the largest multiple k of m within n, then sum = m * k * (k + 1) / 2 using arithmetic progression.

What if m is greater than n?

If m > n, no integers are divisible by m, so the difference is simply the sum of 1 to n.

Can I solve Divisible and Non-divisible Sums Difference without loops?

Yes, using arithmetic progression formulas allows an O(1) solution without any iteration.

What mistakes do candidates often make with this math-driven solution?

They often miscount multiples of m, use loops unnecessarily, or subtract sums in the wrong order.

terminal

Solution

Solution 1: Simulation

We traverse every number in the range $[1, n]$. If it is divisible by $m$, we subtract it from the answer. Otherwise, we add it to the answer.

1

2

3

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

Continue Practicing

#2867 count valid paths in a tree #2864 maximum odd binary number #2862 maximum element sum of a complete subset of indices