{x}
blog image

Find Triangular Sum of an Array

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.

 

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 <= 1000
  • 0 <= nums[i] <= 9

Solution Explanation: Find Triangular Sum of an Array

This problem asks us to iteratively reduce an array by summing adjacent elements modulo 10 until only one element remains. This final element is the "triangular sum."

Approach: Simulation

The most straightforward approach is to simulate the process directly. We iterate, creating new arrays in each step until only one element is left.

Algorithm:

  1. Base Case: If the array has only one element, return that element.
  2. Iteration: Create a new array of size n-1, where n is the current array's size.
  3. Summation and Modulo: For each index i from 0 to n-2, calculate (nums[i] + nums[i+1]) % 10 and store the result in the new array.
  4. Replacement: Replace the original nums array with the newly created array.
  5. Repetition: Repeat steps 1-4 until only one element remains in the array.
  6. Return: Return the single remaining element.

Time Complexity Analysis:

The outer loop runs n-1 times (where n is the initial array length). The inner loop runs n-1, n-2, ..., 1 times, respectively. This leads to a total number of operations proportional to the sum of integers from 1 to n-1, which is approximately n(n-1)/2. Therefore, the time complexity is O(n²).

Space Complexity Analysis:

In the simulation approach, we create new arrays in each iteration. While this seems to imply O(n²) space complexity, we can optimize it to O(1). Instead of creating new arrays, we can modify the existing array in place. This is achieved by iterating through the array from the beginning and overwriting the elements directly.

Code Implementation (Python)

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

This optimized Python code directly modifies the nums list, achieving a space complexity of O(1) while maintaining the O(n²) time complexity due to the nested loop structure. Other languages would have similar implementations, with only minor syntactic changes. For instance, the Java version would use ArrayList initially and then resize it in each iteration, which could potentially affect space complexity, but this can also be optimized in place to O(1) similar to the above approach.