LeetCode Entry

2579. Count Total Number of Colored Cells

05.03.2025 medium 2025 kotlin rust

Arithmetic sum

2579. Count Total Number of Colored Cells medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/915

Problem TLDR

Arithmetic sum #medium #math

Intuition

x.webp The diagonal wall grows one item at a time.


    // 1
    // 1 + 4 = 5
    // 5 + 8 = 13
    // 13 + 12 = f(n - 1) + n * 2 + (n - 2) * 2

Arithmetic sum of n:

coloredCells(n) = coloredCells(1) + ∑(i=2 to n) (i*4 - 4)
                = 1 + 4*∑(i=2 to n) i - 4*(n-1)
                = 1 + 4*[n(n+1)/2 - 1] - 4*(n-1)
                = 1 + 4*[n(n+1)/2 - 1] - 4n + 4
                = 1 + 2n(n+1) - 4 - 4n + 4
                = 1 + 2n² + 2n - 4 - 4n + 4
                = 2n² - 2n + 1

Approach

  • draw, notice the pattern, write the code
  • ask claude for the math formula

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\) for the recursion

Code


    fun coloredCells(n: Int): Long =
        if (n < 2) 1 else coloredCells(n - 1) + n * 4 - 4



    pub fn colored_cells(n: i32) -> i64 {
        let n = n as i64; 2 * n * n - 2 * n + 1
    }



    long long coloredCells(int n) {
       long long x = n; return 2 * x * x - 2 * x + 1;
    }