Divisible and Non-divisible Sums Difference
EasyPrompt
You are given positive integers n and m.
Define two integers as follows:
num1: The sum of all integers in the range[1, n](both inclusive) that are not divisible bym.num2: The sum of all integers in the range[1, n](both inclusive) that are divisible bym.
Return the integer num1 - num2.
Example 1:
Input: n = 10, m = 3
Output: 19
Explanation: In the given example:
- Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.
- Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18.
We return 37 - 18 = 19 as the answer.Example 2:
Input: n = 5, m = 6
Output: 15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.
- Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0.
We return 15 - 0 = 15 as the answer.Example 3:
Input: n = 5, m = 1
Output: -15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 1 are [], num1 is the sum of those integers = 0.
- Integers in the range [1, 5] that are divisible by 1 are [1,2,3,4,5], num2 is the sum of those integers = 15.
We return 0 - 15 = -15 as the answer.
Constraints:
1 <= n, m <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly follows the problem description by iterating through all numbers from 1 to n. It maintains two separate sums: one for numbers divisible by m (num2) and one for numbers not divisible by m (num1). For each number, it determines which category it falls into and updates the corresponding sum. Finally, it calculates and returns the difference num1 - num2.
Algorithm
- Initialize two integer variables,
num1andnum2, to 0. - Loop through each integer
ifrom 1 ton. - Inside the loop, check if
iis divisible bymusing the modulo operator (i % m == 0). - If
iis divisible bym, additonum2. - Otherwise, add
itonum1. - After the loop finishes, return the result of
num1 - num2.
Walkthrough
The most straightforward way to solve this problem is to simulate the process described. We can use a loop that runs from 1 to n. In each iteration, we check if the current number i is divisible by m. We use two variables, num1 and num2, initialized to zero, to accumulate the sums. If i % m is 0, we add i to num2; otherwise, we add it to num1. After the loop has processed all numbers up to n, the final answer is simply num1 - num2.
class Solution { public int differenceOfSums(int n, int m) { int num1 = 0; // Sum of integers not divisible by m int num2 = 0; // Sum of integers divisible by m for (int i = 1; i <= n; i++) { if (i % m == 0) { num2 += i; } else { num1 += i; } } return num1 - num2; }}Complexity
Time
O(n) - The algorithm iterates through `n` numbers once. The operations inside the loop (modulo, addition) take constant time. Therefore, the total time complexity is linear with respect to `n`.
Space
O(1) - The memory usage is constant as it only requires a few variables to store the sums and the loop counter, regardless of the input size `n`.
Trade-offs
Pros
Very simple to understand and implement.
It's a direct translation of the problem statement into code, making it easy to verify its correctness.
Cons
Less efficient for very large values of
ncompared to the mathematical approach.Performs
niterations, which can be slow ifnis extremely large (though acceptable for the given constraints).
Solutions
Solution
class Solution {public int differenceOfSums(int n, int m) { int ans = 0; for (int i = 1; i <= n; ++i) { ans += i % m == 0 ? -i : i; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.