Problem Description

You are given two positive integers n and m.

The problem asks you to calculate the difference between two sums:

1. num1: The sum of all integers from 1 to n that are not divisible by m
2. num2: The sum of all integers from 1 to n that are divisible by m

Your task is to return the value of num1 - num2.

For example, if n = 10 and m = 3:

• Numbers from 1 to 10 that are not divisible by 3: 1, 2, 4, 5, 7, 8, 10
  • Their sum (num1) = 1 + 2 + 4 + 5 + 7 + 8 + 10 = 37
• Numbers from 1 to 10 that are divisible by 3: 3, 6, 9
  • Their sum (num2) = 3 + 6 + 9 = 18
• The answer would be 37 - 18 = 19

The solution iterates through all numbers from 1 to n. For each number i, if it's divisible by m (i.e., i % m == 0), it subtracts the number from the running total. Otherwise, it adds the number to the running total. This effectively calculates num1 - num2 in a single pass.

Intuition

The straightforward approach would be to calculate num1 and num2 separately by iterating through the range twice or maintaining two separate sums. However, we can optimize this by recognizing a key pattern in the calculation.

When we compute num1 - num2, we're essentially:

• Adding numbers that are not divisible by m
• Subtracting numbers that are divisible by m

This means for each number i in the range [1, n]:

• If i is not divisible by m, it contributes +i to our final answer
• If i is divisible by m, it contributes -i to our final answer

Instead of maintaining two separate sums and then subtracting them, we can directly compute the final result in a single pass. For each number, we check if it's divisible by m using the modulo operator (i % m). If the remainder is 0 (meaning it's divisible), we subtract it; otherwise, we add it.

The clever part of the solution uses the fact that i % m evaluates to 0 (falsy) when i is divisible by m, and a non-zero value (truthy) otherwise. This allows us to write a concise conditional expression: i if i % m else -i, which adds i when it's not divisible by m and subtracts i when it is divisible by m.

This approach reduces both the code complexity and ensures we only need one iteration through the range, making the solution both elegant and efficient.

Learn more about Math patterns.

Solution Approach

The solution uses a simulation approach where we traverse every number in the range [1, n] and apply the appropriate operation based on divisibility by m.

Implementation Steps:

1. Iterate through the range: We loop through all integers from 1 to n (inclusive) using range(1, n + 1).

2. Check divisibility and accumulate: For each number i in the range:

   • We check if i is divisible by m using the modulo operator i % m
   • If i % m equals 0 (number is divisible by m), we subtract it from our running total
   • If i % m is non-zero (number is not divisible by m), we add it to our running total

3. Return the result: The accumulated sum directly gives us num1 - num2.

Code Implementation:

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

The solution leverages Python's generator expression with a conditional operator:

• i if i % m else -i: This expression evaluates to i when i % m is non-zero (truthy), meaning the number is not divisible by m. It evaluates to -i when i % m is 0 (falsy), meaning the number is divisible by m.
• The sum() function then accumulates all these values, effectively calculating the difference between the sum of non-divisible numbers and divisible numbers in a single pass.

Time Complexity: O(n) - We iterate through all numbers from 1 to n once.

Space Complexity: O(1) - We only use a constant amount of extra space for the calculation.

Example Walkthrough

Let's walk through the solution with n = 5 and m = 2:

Step 1: Identify the numbers

• Range: [1, 2, 3, 4, 5]
• Numbers divisible by 2: [2, 4]
• Numbers not divisible by 2: [1, 3, 5]

Step 2: Apply the solution logic

Our solution iterates through each number and applies the conditional: i if i % m else -i

Step 3: Verify the result

• num1 (sum of non-divisible): 1 + 3 + 5 = 9
• num2 (sum of divisible): 2 + 4 = 6
• num1 - num2 = 9 - 6 = 3 ✓

The solution correctly returns 3 by adding non-divisible numbers and subtracting divisible numbers in a single pass through the range.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the given integer. This is because the code iterates through all integers from 1 to n exactly once using the range function range(1, n + 1). For each integer i in this range, it performs a constant-time operation (checking divisibility by m and either adding or subtracting the value).

The space complexity is O(1). Although the code uses a generator expression (i if i % m else -i for i in range(1, n + 1)), the sum() function processes it iteratively without storing all values in memory at once. The generator yields one value at a time, and only a constant amount of extra space is used to maintain the running sum and loop variables.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Other Languages

While Python handles arbitrarily large integers automatically, implementing this solution in languages like C++ or Java could lead to integer overflow for large values of n.

Problem Example:

• If n = 10^9, the sum of numbers from 1 to n is approximately n*(n+1)/2 ≈ 5*10^17, which exceeds the range of 32-bit integers and even 64-bit integers in some cases.

Solution:

• Use appropriate data types (long long in C++, long in Java)
• Consider using mathematical formulas to avoid iteration when possible

2. Inefficient for Large Values of n

The O(n) time complexity means iterating through potentially billions of numbers when n is large, which can be slow.

Optimized Mathematical Approach:

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # Calculate total sum using formula: n*(n+1)/2
        total_sum = n * (n + 1) // 2
      
        # Calculate sum of multiples of m
        # Numbers divisible by m: m, 2m, 3m, ..., km where k = n//m
        k = n // m
        sum_divisible = m * k * (k + 1) // 2
      
        # num1 = total_sum - sum_divisible (sum of non-divisible)
        # num2 = sum_divisible (sum of divisible)
        # Result = num1 - num2 = (total_sum - sum_divisible) - sum_divisible
        return total_sum - 2 * sum_divisible

This reduces time complexity from O(n) to O(1).

3. Misunderstanding the Ternary Expression Logic

The expression i if i % m else -i might be confusing because it relies on Python's truthiness:

• i % m returns 0 (falsy) when divisible
• i % m returns non-zero (truthy) when not divisible

Clearer Alternative:

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        result = 0
        for i in range(1, n + 1):
            if i % m == 0:
                result -= i  # Subtract if divisible
            else:
                result += i  # Add if not divisible
        return result

4. Edge Case Handling

While the problem states n and m are positive integers, always verify:

• What happens when m > n? (All numbers are not divisible by m)
• What happens when m = 1? (All numbers are divisible by m, result will be negative)

These edge cases work correctly with the given solution but understanding them helps prevent bugs in modified versions.