yokolet's notelets

  1. Others
  2. Find Triangular Sum of an Array

Others

Find Triangular Sum of an Array

Problem Description

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.

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 9

Examples

Example 1:
Input: nums = [1,2,3,4,5]
Output: 8

1, 2, 3, 4, 5
3, 5, 7, 9
8, 2, 6
0, 8,
8
Example 2:
Input: nums = [5]
Output: 5

How to Solve

This is a math problem. The brute force solution in Python barely passes all tests, however, it is very slow. To finds an optimal solution, some mathematical insight is required.

The mathematical solution is from combination idea: each number is multiplied by the number of routes to the top. In the solution, this number is “cnk”. Additionally, the calculation uses: (a % 10 + b % 10) % 10 = (a + b) % 10.

For a reference, Python has a brute force solution as well.

Solution

  • 
    
  • 
    
  • 
    
  • class FindTriangularSumOfAnArrayMath:
        def triangularSum(self, nums: List[int]) -> int:
            n = len(nums)-1
            total = 0
            cnk = 1
            for i in range(len(nums)):
                total += nums[i] * cnk
                total %= 10
                cnk = cnk * (n-i) // (i+1)
            return total
    
    class FindTriangularSumOfAnArrayBF:
        def triangularSum(self, nums: List[int]) -> int:
            n, prev = len(nums), nums
            for _ in range(n - 1):
                cur = []
                for i in range(len(prev) - 1):
                    cur.append((prev[i] + prev[i + 1]) % 10)
                prev = cur
            return prev[0]
    
  • # @param {Integer[]} nums
    # @return {Integer}
    def triangular_sum(nums)
      n = nums.length - 1
      total, cnk = 0, 1
      nums.each_with_index do |num, i|
        total += num * cnk
        total %= 10
        cnk = cnk * (n - i) / (i + 1)
      end
      total
    end
    

Complexities

  • Time: O(n) – math solution, O(n^2) – brute force solution
  • Space: O(1) – math solution, O(n) – brute force solution
Medium
Math
Array