DDSA Solutions

2894. Divisible and Non-divisible Sums Difference

Time: O(n/m)
Space: O(1)
Advertisement

Intuition

Divisible and non-divisible sums difference. Sum all nums 1..n minus 2*(sum of multiples of m).

Algorithm

  1. 1Total = n*(n+1)/2. Sum of multiples of m up to n: m*(1+2+...+k) where k=floor(n/m). = m*k*(k+1)/2.
  2. 2Answer = total - 2 * multiples_sum.

Common Pitfalls

  • Answer = (sum of non-divisible) - (sum of divisible). Direct formula.
2894.cs
C#
// Approach: Sum all 1..n; subtract 2 * sum of multiples of m; result = total - 2*mSum.
// Time: O(n/m) Space: O(1)

public class Solution
{
    public int DifferenceOfSums(int n, int m)
    {
        int sum = (1 + n) * n / 2;
        int num2 = GetDivisibleSum(n, m);
        int num1 = sum - num2;
        return num1 - num2;
    }

    // Returns the sum of all the integers in [1, n] that are divisible by m.
    private int GetDivisibleSum(int n, int m)
    {
        int last = n / m * m;
        if (last == 0)
            return 0;
        int first = m;
        int count = (last - first) / m + 1;
        return (first + last) * count / 2;
    }
}
Advertisement
Was this solution helpful?