Divisible and Non-divisible Sums Difference

easy math divisibility modulo

Problem

Given positive integers n and m, look at every integer in the range [1, n]. Let num1 be the sum of those not divisible by m, and num2 the sum of those divisible by m. Return num1 − num2.

Inputn = 10, m = 3

Output19

Not divisible by 3: [1,2,4,5,7,8,10] sum = 37. Divisible by 3: [3,6,9] sum = 18. Answer = 37 − 18 = 19.

n (1 to 1000)

m (1 to 1000)

def differenceOfSums(n, m):
    num1 = 0   # sum of numbers NOT divisible by m
    num2 = 0   # sum of numbers divisible by m
    for i in range(1, n + 1):
        if i % m == 0:
            num2 += i
        else:
            num1 += i
    return num1 - num2

function differenceOfSums(n, m) {
  let num1 = 0; // sum of numbers NOT divisible by m
  let num2 = 0; // sum of numbers divisible by m
  for (let i = 1; i <= n; i++) {
    if (i % m === 0) {
      num2 += i;
    } else {
      num1 += i;
    }
  }
  return num1 - num2;
}

int differenceOfSums(int n, int m) {
    int num1 = 0; // sum of numbers NOT divisible by m
    int num2 = 0; // sum of numbers divisible by m
    for (int i = 1; i <= n; i++) {
        if (i % m == 0) {
            num2 += i;
        } else {
            num1 += i;
        }
    }
    return num1 - num2;
}

int differenceOfSums(int n, int m) {
    int num1 = 0; // sum of numbers NOT divisible by m
    int num2 = 0; // sum of numbers divisible by m
    for (int i = 1; i <= n; i++) {
        if (i % m == 0) {
            num2 += i;
        } else {
            num1 += i;
        }
    }
    return num1 - num2;
}

Explanation

This is a direct counting problem: we simply scan every integer from 1 to n and drop each one into one of two buckets depending on whether m divides it.

The test for divisibility is the modulo operator: i % m == 0 is true exactly when i is a multiple of m. When it is, we add i to num2 (the divisible sum); otherwise we add it to num1 (the non-divisible sum).

After the loop, the answer is num1 - num2. Because each number lands in exactly one bucket, the two sums together cover the whole range, so nothing is double-counted or missed.

Example: for n = 10, m = 3 the multiples of 3 are 3, 6, 9 (sum 18) and everything else sums to 37, giving 37 - 18 = 19.

A closed-form shortcut exists: the full sum 1 + 2 + … + n equals n(n+1)/2, and the multiples of m are m + 2m + … up to n. Subtracting twice the divisible sum from the total also yields the answer in O(1), but the linear scan shown here is the clearest to follow and is fast enough for n ≤ 1000.

Time: O(n) Space: O(1)