Abstract / Summary

Given an array and a divisor, compute the difference between the sum of elements not divisible by the divisor and the sum of those that are.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 91% (300k+ submissions).

Typical patterns to solve this problem:

• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single method differenceOfSums. The method receives two integer parameters, n and m, and computes the arithmetic difference between the sum of all integers from 1 to n that are not divisible by m and the sum of those that are divisible by m. The algorithm follows a straightforward iterative approach, accumulating two separate totals while traversing the range once.

Core Logic

The method begins by initializing two accumulator variables, num1 and num2, to zero. These variables hold the running totals for non-multiples and multiples of m, respectively.

num1 = 0
num2 = 0

A for loop iterates over the inclusive range [1, n]. For each integer i, the code evaluates the remainder of i divided by m. If the remainder is zero, i is a multiple of m and is added to num2; otherwise, it contributes to num1.

for i in range(1, n + 1):
    if i % m == 0:
        num2 += i
    else:
        num1 += i

After the loop completes, the method returns the difference between the two accumulated sums.

return num1 - num2

Edge-Case Handling

The loop construct naturally accommodates the situation where n is zero or negative. In such cases, the range range(1, n + 1) yields no elements, leaving both accumulators at their initial value of zero, and the method returns 0. This behavior ensures that the function produces a mathematically consistent result without requiring explicit conditional checks for empty ranges.

When m equals 1, every integer in the range satisfies i % m == 0. Consequently, all values are aggregated into num2, while num1 remains zero, and the final result is the negated sum of the first n natural numbers. Conversely, if m exceeds n, no integer in the range can be a multiple of m; the condition i % m == 0 never holds, and the method returns the sum of the first n natural numbers unchanged.

Performance Characteristics

The algorithm processes each integer from 1 to n exactly once, performing a constant-time modulo operation and a simple addition per iteration. This linear traversal yields a runtime that scales proportionally with the magnitude of n. Memory usage remains constant throughout execution because only two integer variables are maintained regardless of input size; no auxiliary data structures are allocated.

By avoiding the creation of intermediate collections or the use of recursion, the implementation benefits from minimal overhead and predictable performance. The direct use of integer arithmetic ensures that each step executes efficiently on typical Python runtimes.

Imagine having a big pile of number cards lined up from one all the way up to a special number called n. The goal is to sort these cards into two different baskets.

The first basket is for numbers that cannot be shared equally by the number m. The second basket is for the numbers that can be shared perfectly by m. To figure out where each card goes, a small helper looks at one card at a time. If the card divides perfectly by m, it slides into the second basket. If it does not, it goes into the first basket.

Once all the cards are put away, both baskets are emptied out to see how much they add up to. The first basket holds a big total, and the second basket holds a smaller total. Finding out how much bigger the first bunch is compared to the second bunch is the final step.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	Python		C++		TS
	WalkCCC		Java	Python		C++
	leetcode.ca		Java	Python	Go	C++	Rust	TS
	Progiez		Java	Python		C++
github	chandansgowda			Python
	charles-wangkai		Java
	everthis	JS
	fsq					C++
	JoshCrozier	JS
	muhammadfarhankt				Go
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
muhammadfarhankt	Go
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality