Скачать или смотреть # 30.09.2025 [2221. Find Triangular Sum of an Array]

30.09.2025
[2221. Find Triangular Sum of an Array](https://leetcode.com/problems/find-tr...) medium
[blog post](https://leetcode.com/problems/find-tr...)
[substack](https://open.substack.com/pub/dmitrii...)
[youtube](   • # 30.09.2025 [2221. Find Triangular Sum of...  )




#### Join me on Telegram

https://t.me/leetcode_daily_unstoppab...

#### 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
```j
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/Binomia...)
`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
https://dmitrysamoylenko.com/2023/07/...