Find Triangular Sum of an Array

Medium

Asked by:

28 views

Topics:

Arrays

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:

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.
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.
Replace the array nums with newNums.
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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array?
Can the input array contain negative numbers?
Is the input array guaranteed to be non-empty?
What should I return if the input array is empty?
Are the array elements guaranteed to be integers?

Brute Force Solution

Approach

The brute force way to find the triangular sum is to repeatedly shrink the set of numbers until we are left with just one. We do this by adding up adjacent numbers and taking the remainder after dividing by ten.

Here's how the algorithm would work step-by-step:

Start with the original list of numbers.
Create a new list. The first number in the new list is created by adding the first two numbers from the original list, and finding the remainder after dividing by ten.
The second number in the new list is created by adding the second and third numbers from the original list, and finding the remainder after dividing by ten.
Continue this process, creating a new number for each pair of adjacent numbers in the original list. The new list will have one fewer number than the original.
Repeat this process using the new list as the original. Keep creating smaller and smaller lists in the same way.
Eventually, you will have a list containing only one number. That number is the triangular sum.

Code Implementation

def triangular_sum(numbers):
    numbers_to_reduce = numbers

    while len(numbers_to_reduce) > 1:
        new_numbers = []
        # Reduce the array by summing adjacent elements
        for index in range(len(numbers_to_reduce) - 1):

            sum_of_adjacent_numbers = numbers_to_reduce[index] + numbers_to_reduce[index + 1]
            remainder = sum_of_adjacent_numbers % 10
            new_numbers.append(remainder)

        # Update numbers to reduce for the next iteration
        numbers_to_reduce = new_numbers

    return numbers_to_reduce[0]

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm iteratively reduces the array's size. In the first iteration, we process n elements to produce an array of size n-1. In the second iteration, we process n-1 elements to produce an array of size n-2, and so on, until we are left with a single element. Thus, the total number of operations is proportional to n + (n-1) + (n-2) + ... + 1. This sum is equivalent to n * (n+1) / 2, which simplifies to O(n²).

Space Complexity

O(N) – The provided algorithm repeatedly creates new lists. In the worst-case scenario, we create lists of size N-1, N-2, ..., 1. However, because the algorithm overwrites the initial list with the subsequent reduced lists (based on the plain english instructions), the space required is primarily determined by the size of the largest list created, which is on the order of the original list's size. Therefore, the auxiliary space required to store these lists is proportional to the input size N, which contains the numbers. Thus, the space complexity is O(N).

Optimal Solution

Approach

The most efficient way to find the final sum involves repeatedly reducing the array until a single number remains. Each reduction step calculates a new array where each element is the sum of two adjacent elements from the previous array, with a critical adjustment. This clever transformation avoids redundant calculations.

Here's how the algorithm would work step-by-step:

Begin with the original set of numbers.
Create a new, smaller set of numbers. The first number in this new set is calculated by adding the first and second number of original set, then taking only the last digit from the result (think of only remembering the ones place).
Continue creating the new set. Each number in this new set comes from adding two side-by-side numbers in the original set, again only paying attention to the last digit of the result.
Repeat the process. Use the new set of numbers to create an even smaller set of numbers, following the same addition and digit-keeping rule.
Keep going until you are left with just one number. That single number is the answer you are looking for.

Code Implementation

def findTriangularSum(numbers):
    while len(numbers) > 1:
        new_numbers = []

        # Iterate through the array to create the next level
        for i in range(len(numbers) - 1):

            # Sum adjacent elements and take the last digit
            element_sum = (numbers[i] + numbers[i + 1]) % 10
            new_numbers.append(element_sum)

        # Update the array with the new reduced array.
        numbers = new_numbers

    # The final element is the triangular sum.
    return numbers[0]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iteratively reduces the input array nums until only one element remains. In each iteration, a new array is constructed by summing adjacent elements of the previous array, taking the modulo 10 of the result. The size of the array decreases by one in each iteration. Therefore, the number of iterations is n-1, where n is the size of the original array. The first iteration takes O(n) time, the second O(n-1), and so on. This results in a total time complexity proportional to n + (n-1) + (n-2) + ... + 1, which is the sum of an arithmetic series and equals n(n+1)/2. Thus, the overall time complexity simplifies to O(n²).

Space Complexity

O(N) – The algorithm repeatedly creates a new array to store the intermediate sums. In the worst-case scenario, where the input array nums has size N, the first reduction creates an array of size N-1, the next N-2, and so on. While these arrays are overwritten, the algorithm requires storing an array of potentially size N at each step of the calculation. Therefore, the auxiliary space used is proportional to the size of the initial array, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the array is null or empty, as there's no sum to compute.
Array with a single element	Return the single element as the triangular sum when the array has only one element.
Array with only two elements	Calculate the sum of the two elements modulo 10, return the result as the final triangular sum.
Large array size exceeding available memory	Implement the algorithm in-place to minimize memory usage and avoid out-of-memory errors.
Array with all elements being 9	The algorithm should correctly reduce the sum to a single digit, even when all intermediate sums are close to multiples of 10.
Array with elements close to the maximum integer value.	The intermediate sums could potentially overflow, ensure the language handles this correctly or cast to a larger data type if necessary before performing the modulo operation.
Negative numbers present in the input array	Add 10 before taking the modulo to ensure a positive result, which prevents issues with negative remainders.
Array with elements consisting of a repeating single digit.	The algorithm handles this case correctly because it repeatedly reduces the sum until a single digit remains.

Null or empty input array

How to Handle:

Return 0 if the array is null or empty, as there's no sum to compute.

Array with a single element

How to Handle:

Return the single element as the triangular sum when the array has only one element.

Array with only two elements

How to Handle:

Calculate the sum of the two elements modulo 10, return the result as the final triangular sum.

Large array size exceeding available memory

How to Handle:

Implement the algorithm in-place to minimize memory usage and avoid out-of-memory errors.

Array with all elements being 9

How to Handle:

The algorithm should correctly reduce the sum to a single digit, even when all intermediate sums are close to multiples of 10.

Array with elements close to the maximum integer value.

How to Handle:

The intermediate sums could potentially overflow, ensure the language handles this correctly or cast to a larger data type if necessary before performing the modulo operation.

Negative numbers present in the input array

How to Handle:

Add 10 before taking the modulo to ensure a positive result, which prevents issues with negative remainders.

Array with elements consisting of a repeating single digit.

How to Handle:

The algorithm handles this case correctly because it repeatedly reduces the sum until a single digit remains.