Find Triangular Sum of an Array

main.md

Question

Approach

I solve the triangular sum problem by recognizing that the process is equivalent to weighting each element in the array by a binomial coefficient. Instead of simulating all reductions, I compute the binomial coefficients for row n-1, multiply each nums[i] by its coefficient, sum them up, and take the result modulo 10.

Implementation

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        n = len(nums)
        coeff = [1]
        
        for row in range(1, n):
            new_coeff = [1] * (row + 1)
            for j in range(1, row):
                new_coeff[j] = (coeff[j-1] + coeff[j]) % 10
            coeff = new_coeff
        
        ans = sum(c * v for c, v in zip(coeff, nums)) % 10
        return ans

Complexities

• Time: O(n)
• Space: O(1)