Divisible and Non-Divisible Sums Difference — Solution
Divisible and Non-Divisible Sums Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Divisible and Non-Divisible Sums Difference is an easy coding problem on math, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Math
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given positive integers n and m.
Let num1 be the sum of the integers in [1, n] that are not divisible by m, and num2 the sum of those that are.
Return num1 - num2.
Example 1
Input: n = 10, m = 3
Output: 19
Explanation: num1 = 1+2+4+5+7+8+10 = 37 and num2 = 3+6+9 = 18.
Example 2
Input: n = 5, m = 6
Output: 15
Explanation: Nothing in range is divisible by 6, so num2 is 0.
Example 3
Input: n = 5, m = 1
Output: -15
Explanation: Everything is divisible by 1, so num1 is 0.
Constraints
1 <= n, m <= 1000
Hints for Divisible and Non-Divisible Sums Difference
Hint 1
A direct loop over
1..nis fast enough at these limits.Hint 2
Add each value to one accumulator or the other based on
i % m.Hint 3
A closed form also exists:
total - 2 · (sum of multiples of m).
How to solve Divisible and Non-Divisible Sums Difference
Partition [1, n] by divisibility and difference the two sums. The range is small, so the honest loop is clearest.
Approach
- Loop
ifrom 1 ton. - Add
itonum2wheni % m == 0, otherwise tonum1. - Return
num1 - num2.
Why it works
The two sets partition the range, so num1 + num2 is the full triangular sum and the difference is well defined. The closed form follows: num1 - num2 = total - 2·num2.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The answer can be negative —
m = 1puts everything innum2. - Starting the loop at 0 adds a harmless zero but muddies the divisibility count.
Reference solution
Python
def differenceOfSums(n: int, m: int) -> int:
num1 = 0
num2 = 0
for i in range(1, n + 1):
if i % m == 0:
num2 += i
else:
num1 += i
return num1 - num2Java
public static int differenceOfSums(int n, int m) {
int num1 = 0, num2 = 0;
for (int i = 1; i <= n; i++) {
if (i % m == 0) num2 += i;
else num1 += i;
}
return num1 - num2;
}C++
int differenceOfSums(int n, int m) {
int num1 = 0, num2 = 0;
for (int i = 1; i <= n; i++) {
if (i % m == 0) num2 += i;
else num1 += i;
}
return num1 - num2;
}JavaScript
var differenceOfSums = function(n, m) {
let num1 = 0, num2 = 0;
for (let i = 1; i <= n; i++) {
if (i % m === 0) num2 += i;
else num1 += i;
}
return num1 - num2;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.