2894. Divisible and Non-divisible Sums Difference
Problem Description
In this problem, we are given two positive integers, n
and m
. Our task is to calculate the difference between the sum of all integers from 1 to n
that are not divisible by m
, and the sum of all integers from 1 to n
that are divisible by m
. To clarify, we define two sums:
num1
is the sum of all integers within the range1
ton
that cannot be evenly divided bym
.num2
is the sum of all integers within the same range that can be evenly divided bym
.
The goal is to find the result of num1 - num2
, which will be an integer. For a simple example, if n
is 5 and m
is 2, then num1
(sum of numbers not divisible by 2) would be 1 + 3 + 5 = 9, and num2
(sum of numbers divisible by 2) would be 2 + 4 = 6. Thus, the answer would be 9 - 6 = 3.
Intuition
To solve this problem, we can iterate through all numbers from 1 to n
and categorize them based on whether they are divisible by m
or not. If a number i
is not divisible by m
, we add it to num1
. Otherwise, if it is divisible by m
, we add it to num2
. To find the final answer, we subtract num2
from num1
.
However, instead of maintaining two separate sums and calculating the difference at the end, we can simply keep a running total that adds the value of numbers not divisible by m
and subtracts the value of numbers that are divisible by m
. This approach eliminates the need for separate variables and consolidates the operation into a single expression.
We arrive at this solution approach because we recognize that adding and subtracting can be performed during a single pass through the range of numbers. This way, the solution becomes more efficient and we can immediately obtain the result after the pass without additional calculations.
Learn more about Math patterns.
Solution Approach
The solution provided follows a straightforward simulation approach. This approach is about going through each number in the range [1, n]
one by one and directly applying the logic or operation required by the problem. In programming terms, this is typically done via a for
loop, which iterates through the given range of numbers.
We don't use any additional data structures like arrays or lists to store intermediate results because we only need to keep track of a running total. This running total is updated on each iteration of the loop.
The algorithm can be described in the following steps:
-
Initialize a variable to store the running total. This can start at 0 because initially, we have no numbers to add or subtract.
-
Use a loop to iterate through all numbers from
1
up to and includingn
. In Python, this is done using therange
function, i.e.,range(1, n + 1)
. -
For every number
i
in the range:- If
i
is divisible bym
(i.e.,i % m == 0
), subtracti
from the running total. In Python, the modulo operator%
is used to determine if there is any remainder from the division. A remainder of 0 means the number is divisible. - Otherwise, if
i
is not divisible bym
, addi
to the running total.
- If
-
After the loop completes, return the final running total, which represents
num1 - num2
.
The solution translates this algorithm into a compact Python list comprehension and a generator expression inside the sum
function. This is a common pattern in Python that allows for efficient iteration and computation of sums without the explicit need for a loop structure in the code.
The Python code sum(i if i % m else -i for i in range(1, n + 1))
succinctly represents this process. It iterates over the range, and for each i
, it adds i
to the sum if i
is not divisible by m
and subtracts i
otherwise, directly evaluating our condition in a one-liner.
This solution approach delivers an elegant and efficient way to calculate the desired difference without resorting to multi-step processes or additional memory usage.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we choose n = 7
and m = 3
. Our task is to find the difference between the sum of all integers from 1
to 7
that are not divisible by 3
, and the sum of all integers from 1
to 7
that are divisible by 3
.
To clarify:
- Sum of numbers not divisible by
3
(num1
): 1 + 2 + 4 + 5 + 7 = 19 - Sum of numbers divisible by
3
(num2
): 3 + 6 = 9
We want to find num1 - num2
, which in this case is 19 - 9 = 10
.
Now, according to our solution approach:
-
We start by initializing a variable
total
to store our running total (total = 0
). -
We iterate through all numbers from
1
to7
using a loop. -
As we loop through each number
i
(from1
to7
), we check if it's divisible by3
. If it is not divisible (i % 3 != 0
), we addi
tototal
. If it is divisible (i % m == 0
), we subtracti
fromtotal
.
The calculations would proceed as follows:
- Start with
total = 0
. - i = 1: Not divisible by 3, so
total = total + 1
. - i = 2: Not divisible by 3, so
total = total + 2
. - i = 3: Divisible by 3, so
total = total - 3
. - i = 4: Not divisible by 3, so
total = total + 4
. - i = 5: Not divisible by 3, so
total = total + 5
. - i = 6: Divisible by 3, so
total = total - 6
. - i = 7: Not divisible by 3, so
total = total + 7
.
Adding it all up, we get:
total = 0 + 1 + 2 - 3 + 4 + 5 - 6 + 7 = 10
- After the loop completes,
total
gives us the final result. In this case,total = 10
, which matches our manual calculation (num1 - num2 = 19 - 9 = 10
).
Our Python code for this would look like this:
1total = sum(i if i % 3 else -i for i in range(1, 8))
2print(total) # Output: 10
The code uses a generator expression inside the sum
function to apply the solution approach directly, resulting in an efficient and concise way to compute the answer. The generator expression takes each number in the range, checks if it is divisible by 3, and adds or subtracts it accordingly, performing the entire calculation in a single line.
Solution Implementation
1class Solution:
2 def difference_of_sums(self, n: int, m: int) -> int:
3 """
4 Calculate the difference of sums where the range from 1 to n is considered.
5 For each number i in the range, it is added to the sum if it is not divisible by m,
6 and subtracted if it is divisible by m.
7
8 :param n: The upper limit of the range to calculate the sum for.
9 :param m: The divisor used to determine if a number should be subtracted from the sum.
10 :return: The calculated difference of sums.
11 """
12 # Initialize the total_difference variable to store the cumulative sum
13 total_difference = 0
14
15 # Iterate through the range from 1 to n, inclusive
16 for i in range(1, n + 1):
17 # Check if the current number i is divisible by m
18 if i % m == 0:
19 # If divisible, subtract it from the total_difference
20 total_difference -= i
21 else:
22 # If not divisible, add it to the total_difference
23 total_difference += i
24
25 # Return the calculated total difference of sums
26 return total_difference
27
28# Example usage:
29# solution = Solution()
30# result = solution.difference_of_sums(10, 2)
31# print(result) # The result will be the difference of sums for numbers from 1 to 10 with m=2
32
1class Solution {
2 // Method to calculate the difference between the sum of numbers not divisible by 'm'
3 // and the sum of numbers divisible by 'm' within the range 1 to 'n'
4 public int differenceOfSums(int n, int m) {
5 // Initialize answer to store the final result
6 int answer = 0;
7
8 // Loop through numbers from 1 to 'n'
9 for (int i = 1; i <= n; ++i) {
10 // Check if the current number is divisible by 'm'
11 if (i % m == 0) {
12 // If it is divisible, subtract it from the answer
13 answer -= i;
14 } else {
15 // If not, add it to the answer
16 answer += i;
17 }
18 }
19
20 // Return the computed difference
21 return answer;
22 }
23}
24
1class Solution {
2public:
3 // Function to calculate the difference between the sum of numbers
4 // from 1 to n that are not multiples of m and the sum of numbers
5 // that are multiples of m.
6 int differenceOfSums(int n, int m) {
7 // Variable to store the final result
8 int difference = 0;
9
10 // Iterate over each number from 1 up to and including n
11 for (int i = 1; i <= n; ++i) {
12 // Check if the current number 'i' is not a multiple of 'm'
13 if (i % m != 0) {
14 // if not a multiple, add it to 'difference'
15 difference += i;
16 } else {
17 // if it is a multiple, subtract it from 'difference'
18 difference -= i;
19 }
20 }
21
22 // Return the final calculated difference
23 return difference;
24 }
25};
26
1/**
2 * Calculate the difference between the sum of numbers that are
3 * not multiples of `m` and the sum of numbers that are multiples of `m`,
4 * from 1 to `n`.
5 *
6 * @param {number} n - The upper limit of the range to consider.
7 * @param {number} m - The modulus value for determining multiples.
8 * @return {number} - The difference of sums.
9 */
10function differenceOfSums(n: number, m: number): number {
11 // Initialize the answer to zero.
12 let answer = 0;
13
14 // Iterate over the range from 1 to `n` inclusive.
15 for (let i = 1; i <= n; ++i) {
16 // Add `i` to the answer if `i` is not a multiple of `m`,
17 // otherwise subtract `i` from the answer.
18 answer += i % m ? i : -i;
19 }
20
21 // Return the computed difference of sums.
22 return answer;
23}
24
Time and Space Complexity
The time complexity of the given code is O(n)
, where n
is the given integer. This is because the code iterates a single loop from 1
to n
, performing a constant amount of work for each iteration.
The space complexity of the code is O(1)
. Only a finite number of variables are used, and there is no data structure whose size scales with n
, so the amount of memory used does not grow with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first