Input: n =10, m =3Output: 19Explanation: 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 return37-18=19 as the answer.
Example 2:
1
2
3
4
5
6
Input: n =5, m =6Output: 15Explanation: 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 return15-0=15 as the answer.
Example 3:
1
2
3
4
5
6
Input: n =5, m =1Output: -15Explanation: 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 return0-15=-15 as the answer.
num1: The sum of integers from 1 to n that are not divisible bym.
num2: The sum of integers from 1 to n that are divisible bym.
Finally, return the value of num1 - num2.
We can use the formula for the sum of an arithmetic series to compute the total sums efficiently.
Sum of the first k natural numbers is $\text{Sum} = \frac{k \times (k + 1)}{2}$.
For num2, the sum of integers divisible by m can be expressed as the sum of a sequence $m, 2m, 3m, \ldots, km$, where $k = \lfloor \frac{n}{m} \rfloor$.
Formula: $\text{Sum} = m \times \frac{k \times (k + 1)}{2}$.
Here are the steps we can take:
Compute the total sum of integers ( [1, n] ).
Compute num2 (sum of integers divisible by m using the sequence formula).
Calculate num1 (subtract num2 from the total sum).
classSolution {
publicintdifferenceOfSums(int n, int m) {
// Total sum of numbers from 1 to nint totalSum = (n * (n + 1)) / 2;
// Sum of numbers divisible by mint k = n / m;
int divSum = m * (k * (k + 1)) / 2;
// num1 - num2int ans = totalSum - 2 * divSum;
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defdifferenceOfSums(self, n: int, m: int) -> int:
# Total sum of numbers from 1 to n total_sum = (n * (n +1)) //2# Sum of numbers divisible by m k = n // m
div_sum = m * (k * (k +1)) //2# num1 - num2 ans = total_sum -2* div_sum
return ans