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:
nums comprise of n elements. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n - 1.i, where 0 <= i < n - 1, assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes modulo operator.nums with newNums.Return the triangular sum of nums.
Example 1:
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 <= 10000 <= nums[i] <= 9In #2221 Find Triangular Sum of an Array, you repeatedly replace the array with a new array where each element is the sum of adjacent elements modulo 10. This continues until only one value remains, which is the triangular sum.
A straightforward approach is simulation. At each step, build a new array of length n-1 where next[i] = (nums[i] + nums[i+1]) % 10. Continue shrinking the array until one element remains. This method directly mirrors the process described in the problem.
A more optimized perspective uses combinatorics. The final value can be expressed as a weighted sum of the original elements using binomial coefficients from Pascal’s Triangle. Specifically, each element contributes C(n-1, i) times to the result (modulo 10). Computing these coefficients iteratively allows a faster solution without repeated simulation.
The simulation approach is simple to implement, while the combinatorics insight reduces repeated work and highlights the mathematical structure of the problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Simulation (iteratively reducing array) | O(n^2) | O(1) |
| Combinatorics using binomial coefficients | O(n) | O(1) |
Sahil & Sarra
Use these hints if you're stuck. Try solving on your own first.
Try simulating the entire process.
To reduce space, use a temporary array to update nums in every step instead of creating a new array at each step.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Each reduction step combines adjacent elements, which mirrors how binomial coefficients accumulate in Pascal’s Triangle. After multiple reductions, the contribution of each original element corresponds to a binomial coefficient from the row n−1.
Yes, problems like this appear in technical interviews because they test both simulation skills and mathematical insight. Recognizing the combinatorics pattern can demonstrate deeper problem-solving ability beyond straightforward implementation.
A simple array is sufficient for this problem. In the simulation approach, you repeatedly update or rebuild the array with adjacent sums modulo 10. No advanced data structures are required.
The optimal approach uses combinatorics. The final triangular sum can be expressed as a weighted sum of the original elements using binomial coefficients from Pascal’s Triangle, all taken modulo 10. This avoids repeatedly rebuilding arrays and reduces the time complexity to linear.