# 30.09.2025 [2221. Find Triangular Sum of an Array]

Triangle sum % 10 #medium #simulation

30.09.2025

2221. Find Triangular Sum of an Array medium blog post substack youtube

https://dmitrysamoylenko.com/2023/07/14/leetcode_daily.html

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1128

Problem TLDR

Triangle sum % 10 #medium #simulation

Intuition

The problem is small 1000, O(n^2) simulation is accepted.

The O(n) intuition (from Stefan Pochmann):

• each position get repeated Pascal’s Triangle times

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

Each new row value is a binomial coefficient (https://en.wikipedia.org/wiki/Binomial_coefficient) mC(k+1) = mCk *(n-1-k)/(k+1) Division by /(k+1) can’t be safely done with %10.

Approach

• windows.map = zipWithNext

Complexity

• Time complexity: $$O(n^2)$$

• Space complexity: $$O(n)$$

Code

// 226ms
    fun triangularSum(n: IntArray) = (2..n.size)
    .fold(n.asList()){r,_->r.zipWithNext{a,b->(a+b)%10}}[0]

    fun triangularSum(n: IntArray): Int {
        var f = 1.toBigInteger()
        var r = 0.toBigInteger()
        for ((i, x) in n.withIndex()) {
            r = (r + f * x.toBigInteger()).mod(10.toBigInteger())
            f = f * (n.size - 1 - i).toBigInteger() / (i + 1).toBigInteger()
        }
        return r.toInt()
    }

// 27ms
    pub fn triangular_sum(n: Vec<i32>) -> i32 {
        (1..n.len()).fold(n,|r,t|r.into_iter().tuple_windows().map(|(a,b)|(a+b)%10).collect())[0]
    }