Today’s problem

2894. Divisible and Non-divisible Sums Difference

Intuition

We are given an integer n and a divisor m, and we want to compute the difference between:

1. The sum of numbers from 1 to n that are not divisible by m.
2. The sum of numbers from 1 to n that are divisible by m.

This means we want to partition the numbers 1 to n into two groups based on divisibility by m, sum each group, and return the difference.

Approach

We can solve this problem using two methods:

Method 1: Formula-Based

• Use the formula for the sum of the first n natural numbers: n * (n + 1) // 2 to get the total sum.
• Count how many numbers from 1 to n are divisible by m: k = n // m.
• The divisible numbers are: m, 2m, ..., km, and their sum is m * (1 + 2 + ... + k) = m * (k * (k + 1) // 2).
• Subtract the divisible sum from the total to get the sum of non-divisible numbers, then subtract.

Method 2: Brute-Force Iteration

• Iterate from 1 to n.
• If the number is divisible by m, add it to num2.
• Otherwise, add it to num1.
• Return the difference num1 - num2.

Complexity

• Time complexity:

  • Method 1: $O(1)$ (constant time using formulas)
  • Method 2: $O(n)$ (linear time iteration)

• Space complexity:

  • Both methods: $O(1)$ (only a few variables used)

Code

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # Method 1: Formula-Based
        total_sum = n * (n + 1) // 2
        k = n // m
        divisible_sum = m * (k * (k + 1) // 2)
        return total_sum - divisible_sum

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # Method 2: Brute-Force Iteration
        num1, num2 = 0, 0
        for i in range(1, n + 1):
            if i % m == 0:
                num2 += i
            else:
                num1 += i
        return num1 - num2

Advertisement

For more solutions, please visit My blog