Find Triangular Sum of an Array
Problem
Each round, replace nums with a new array whose i-th element is (nums[i] + nums[i+1]) mod 10. Repeat until one element is left and return it.
nums = [1, 2, 3, 4, 5]8def triangular_sum(nums):
while len(nums) > 1:
nums = [(nums[i] + nums[i + 1]) % 10 for i in range(len(nums) - 1)]
return nums[0]function triangularSum(nums) {
while (nums.length > 1) {
const next = [];
for (let i = 0; i < nums.length - 1; i++) {
next.push((nums[i] + nums[i + 1]) % 10);
}
nums = next;
}
return nums[0];
}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];
}
}int triangularSum(vector<int>& nums) {
int n = nums.size();
while (n > 1) {
for (int i = 0; i < n - 1; i++) {
nums[i] = (nums[i] + nums[i + 1]) % 10;
}
n--;
}
return nums[0];
}Explanation
This problem asks us to repeatedly fold the array down until just one number is left. The solution does exactly that, literally simulating each round step by step.
In one round we build a shorter array: each new value is the sum of two neighbours, taken mod 10 so it stays a single digit. We use (nums[i] + nums[i + 1]) % 10 for every adjacent pair, which gives an array one element smaller than before.
We keep looping while len(nums) > 1, replacing the array each time. Once it shrinks to a single element, that element is the answer, so we return nums[0].
Example: [1, 2, 3, 4, 5]. First round gives [3, 5, 7, 9] (since 1+2=3, 2+3=5, and so on). Next [8, 2, 6], then [0, 8], then [8]. The final answer is 8.
Because each round shortens the array by one and we do work proportional to its length, the total effort is roughly n + (n-1) + ... + 1, which is why this runs in O(n²) time.