Problem Statement in English

You’re given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).

The triangular sum of nums is the single digit value obtained by performing the following operation until there is only one element left in nums:

  1. Create a new array new_nums of the same length as nums.
  2. For each index i in nums, set new_nums[i] to the sum of nums[i] and nums[i + 1] (modulo 10).
  3. Replace nums with new_nums.
  4. Repeat until nums has only one element.

Return the triangular sum of nums.

Approach

The problem is straightforward. We need to keep reducing the array until we have a single element left.

Solution in Python


class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        buffer = []

        while len(nums) > 1:
            buffer = []
            for i in range(len(nums) - 1):
                buffer.append((nums[i] + nums[i + 1]) % 10)
            nums = buffer

        return nums[0]

Complexity

  • Time: $O(n^2)$, where $n$ is the length of the input array nums. In the worst case, we may need to perform the reduction operation $n$ times, and each operation takes $O(n)$ time.

  • Space: $O(n)$, for the temporary buffer used to store the intermediate results during the reduction process.

And we are done.