Triangular Sum TikTok Python Interview Question

You are given an integer array nums, where each element in it is a single digit (0-9).

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 integer array newNums of length n - 1.
2. For each index i, assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes the modulo operator.
3. Replace the array nums with newNums.
4. Repeat the entire process starting from step 1.

Return the triangular sum of nums.

Test Case #1:

Input: nums = [1, 3, 5, 7]

1. Iteration #1: Form newNums = [(1 + 3) % 10, (3 + 5) % 10, (5 + 7) % 10] = [4, 8, 2].

2. Iteration #2: Form newNums = [(4 + 8) % 10, (8 + 2) % 10] = [2, 0].

3. Iteration #3: Form newNums = [(2 + 0) % 10] = [2].

The triangular sum of nums is 2.

Test Case #2:

Input: nums = [9, 7, 5, 3]

1. Iteration #1: Form newNums = [(9 + 7) % 10, (7 + 5) % 10, (5 + 3) % 10] = [6, 2, 8].

2. Iteration #2: Form newNums = [(6 + 2) % 10, (2 + 8) % 10] = [8, 0].

3. Iteration #3: Form newNums = [(8 + 0) % 10] = [8].

The triangular sum of nums is 8.

Brute force(simulation)

This is the type of question where you will just do what the problem statement says. We will just follow the rules until we are left with an array with only one number.

Here is the code:

    def triangular_sum(nums):
        while len(nums)>1:
            next_nums = []
            for i in range(1,len(nums)):
                next_nums.append((nums[i-1]+nums[i])%10)
            nums = next_nums
        return nums[0]

Recursive approach

Since there isn't much optimization to do, the interviewer might ask you to solve the problem using multiple approaches during an interview. One other way of solving this problem is through recursion.

Base Case:

In recursion, the base case is the simplest version of the problem where the recursion stops. For this problem, the base case occurs when we are left with just one number in the list. This is the final triangular sum, so we simply return it.

if len(nums) == 1:
    return nums[0]

Recursive Case:

The recursive case is where the problem is broken down into smaller subproblems. Here’s what we do in each recursive step:

1. Create a new list (next_nums) where each element is the sum of two consecutive elements from the original list, modulo 10.
2. Recursively call the triangularSum function on this smaller list (next_nums) until we hit the base case.

next_nums = []
for i in range(1, len(nums)):
    next_nums.append((nums[i-1] + nums[i]) % 10)
return triangular_sum(next_nums)

Here is the full recursive solution:

def triangular_sum(nums):
    # Base case: When there's only one number left
    if len(nums) == 1:
        return nums[0]
    
    '''
    Recursive case: Combine adjacent numbers and 
    make the recursive call.
    '''
    next_nums = []
    for i in range(1, len(nums)):
        next_nums.append((nums[i-1] + nums[i]) % 10)
    
    return triangular_sum(next_nums)