Difficulty: Easy | Acceptance: 91.00% | Paid: No Topics: Math
You are given two positive integers n and m.
Create two integer arrays nums1 and nums2, where:
- nums1[i] is divisible by m if i is divisible by m, and nums1[i] is not divisible by m if i is not divisible by m.
- nums2[i] is divisible by m if i is not divisible by m, and nums2[i] is not divisible by m if i is divisible by m.
Return the absolute difference between the sum of nums1 and the sum of nums2.
- Examples
- Constraints
- Brute Force
- Mathematical Formula
Examples
Example 1:
Input: n = 10, m = 3
Output: 19
Explanation:
nums1 = [0, 0, 0, 3, 0, 0, 6, 0, 0, 9, 0]
nums2 = [0, 1, 2, 0, 4, 5, 0, 7, 8, 0, 10]
The sum of nums1 is 18 and the sum of nums2 is 37.
The absolute difference is |18 - 37| = 19.
Example 2:
Input: n = 5, m = 6
Output: 15
Explanation:
nums1 = [0, 0, 0, 0, 0, 0]
nums2 = [0, 1, 2, 3, 4, 5]
The sum of nums1 is 0 and the sum of nums2 is 15.
The absolute difference is |0 - 15| = 15.
Example 3:
Input: n = 5, m = 1
Output: 15
Explanation:
nums1 = [0, 1, 2, 3, 4, 5]
nums2 = [0, 0, 0, 0, 0, 0]
The sum of nums1 is 15 and the sum of nums2 is 0.
The absolute difference is |15 - 0| = 15.
Constraints
1 <= n <= 10⁹
1 <= m <= 10⁹
Brute Force
Intuition Iterate through all numbers from 1 to n, check divisibility by m, and accumulate sums separately for divisible and non-divisible numbers.
Steps
- Initialize sum1 and sum2 to 0
- Loop from 1 to n
- If current number is divisible by m, add it to sum1, otherwise add to sum2
- Return the absolute difference between sum1 and sum2
python
class Solution:
def differenceOfSums(self, n: int, m: int) -> int:
sum1 = 0
sum2 = 0
for i in range(1, n + 1):
if i % m == 0:
sum1 += i
else:
sum2 += i
return abs(sum1 - sum2)
Complexity
- Time: O(n)
- Space: O(1)
- Notes: Simple but inefficient for large n values up to 10⁹
Mathematical Formula
Intuition Use arithmetic series formulas to calculate sums directly without iteration. The sum of numbers divisible by m forms an arithmetic progression, and the total sum from 1 to n is also a known formula.
Steps
- Calculate k = n / m (number of multiples of m in [1, n])
- Sum of divisible numbers = m * k * (k + 1) / 2
- Total sum from 1 to n = n * (n + 1) / 2
- Sum of non-divisible numbers = Total sum - Sum of divisible numbers
- Return absolute difference
python
class Solution:
def differenceOfSums(self, n: int, m: int) -> int:
k = n // m
sum_divisible = m * k * (k + 1) // 2
total_sum = n * (n + 1) // 2
sum_non_divisible = total_sum - sum_divisible
return abs(sum_divisible - sum_non_divisible)
Complexity
- Time: O(1)
- Space: O(1)
- Notes: Optimal solution using mathematical formulas, handles large values efficiently