Find Triangular Sum of an Array

Problem

You are 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 value of the only element present in nums after the following process terminates:

1. Let nums comprise of n elements. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n - 1.
2. For each index i, where 0 <= i < n - 1, assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes modulo operator.
3. Replace the array nums with newNums.
4. Repeat the entire process starting from step 1.

Return the triangular sum of nums.

Examples

Example 1

graph TB;
	A(1) 
	B(2) 
	C(3) 
	D(4) 
	E(5)

A ~~~ N1:::hidden
A --- C1(3)
B --- C1
B --- E1(5)
C --- E1
C --- G(7)
D --- G
D --- I(9)
E --- I
E ~~~ N2:::hidden

C1 ~~~ N3:::hidden
C1 --- H(8)
E1 --- H
E1 --- B1(2)
G --- B1
G --- F(6)
I --- F
I ~~~ N4:::hidden

H ~~~ N5:::hidden
H --- Z(0)
B1 --- Z
B1 --- H1(8)
F --- H1
F ~~~ N6:::hidden

Z ~~~ N7:::hidden
Z --- H2(8)
H1 --- H2
Z ~~~ N8:::hidden

classDef hidden display:none;

Input: nums = [1,2,3,4,5]
Output: 8
Explanation:
The above diagram depicts the process from which we obtain the triangular sum of the array.

Example 2

Input: nums = [5]
Output: 5
Explanation:
Since there is only one element in nums, the triangular sum is the value of that element itself.

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

Solution

Method 1 – Simulation (Iterative Reduction)

Intuition

The process is similar to repeatedly reducing the array by summing adjacent elements modulo 10, until only one element remains. This is a direct simulation of the problem statement.

Approach

1. While the array has more than one element:
   • Create a new array of length n-1.
   • For each index i, set newNums[i] = (nums[i] + nums[i+1]) % 10.
   • Replace nums with newNums.
2. Return the only element left.

Code

C++

class Solution {
public:
    int triangularSum(vector<int>& nums) {
        while (nums.size() > 1) {
            vector<int> nxt(nums.size() - 1);
            for (int i = 0; i < nxt.size(); ++i)
                nxt[i] = (nums[i] + nums[i+1]) % 10;
            nums = nxt;
        }
        return nums[0];
    }
};

Go

func triangularSum(nums []int) int {
    for len(nums) > 1 {
        nxt := make([]int, len(nums)-1)
        for i := 0; i < len(nxt); i++ {
            nxt[i] = (nums[i] + nums[i+1]) % 10
        }
        nums = nxt
    }
    return nums[0]
}

Java

class Solution {
    public int triangularSum(int[] nums) {
        int n = nums.length;
        while (n > 1) {
            for (int i = 0; i < n-1; i++) {
                nums[i] = (nums[i] + nums[i+1]) % 10;
            }
            n--;
        }
        return nums[0];
    }
}

Kotlin

class Solution {
    fun triangularSum(nums: IntArray): Int {
        var n = nums.size
        while (n > 1) {
            for (i in 0 until n-1) {
                nums[i] = (nums[i] + nums[i+1]) % 10
            }
            n--
        }
        return nums[0]
    }
}

Python

class Solution:
    def triangularSum(self, nums: list[int]) -> int:
        while len(nums) > 1:
            nums = [(nums[i] + nums[i+1]) % 10 for i in range(len(nums)-1)]
        return nums[0]

Rust

impl Solution {
    pub fn triangular_sum(mut nums: Vec<i32>) -> i32 {
        while nums.len() > 1 {
            nums = nums.windows(2).map(|w| (w[0] + w[1]) % 10).collect();
        }
        nums[0]
    }
}

TypeScript

class Solution {
    triangularSum(nums: number[]): number {
        while (nums.length > 1) {
            let nxt: number[] = [];
            for (let i = 0; i < nums.length - 1; i++) {
                nxt.push((nums[i] + nums[i+1]) % 10);
            }
            nums = nxt;
        }
        return nums[0];
    }
}

Complexity

• ⏰ Time complexity: O(n^2), since each reduction step processes one less element, for a total of n + (n-1) + ... + 1 = O(n^2) operations.
• 🧺 Space complexity: O(n), as we create new arrays of decreasing size at each step.