LeetCode Entry

2894. Divisible and Non-divisible Sums Difference

27.05.2025 easy 2025 kotlin rust

Sum non-divisible minus sum divisible

2894. Divisible and Non-divisible Sums Difference easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1001

Problem TLDR

Sum non-divisible minus sum divisible #easy #math

Intuition

I was happy to spot we can do this in a single iteration, sum += x % m ? x : -x

There is an arithmetic math solution however:


    // a + b = n*(n+1)/2
    // b = m * k*(k+1)/2, k = n/m, m, 2m, 3m...km
    // a - b = (a + b) - 2b
    // a - b = n*(n+1)/2 - 2*m*k*(k+1)/2

Approach

  • how short can it be?

Complexity

  • Time complexity: \(O(n)\), or O(1)

  • Space complexity: \(O(1)\)

Code


// 5ms (52 symbols)
    fun differenceOfSums(n: Int, m: Int) =
        (1..n).sumOf { if (it % m < 1) -it else it }



// 0ms (49 symbols)
    fun differenceOfSums(n: Int, m: Int) =
        n * (n + 1) / 2 - n / m * (n / m + 1) * m



// 13ms (47 symbols)
    fun differenceOfSums(n: Int, m: Int) =
        (1..n).sum() - n / m * (n / m + 1) * m



// 12ms (46 symbols)
    fun differenceOfSums(n: Int, m: Int) =
        (1..n).sum() - (1..n/m).sum() * m * 2



// 0ms
    pub fn difference_of_sums(n: i32, m: i32) -> i32 {
        n * (n + 1) / 2 - n / m * (n / m + 1) * m
    }



// 0ms
    int differenceOfSums(int n, int m) {
        return n * (n + 1) / 2 - n / m * (n / m + 1) * m;
    }