2221. Find Triangular Sum of an Array

[mah-shamim]

Topics: Array, Math, Simulation, Combinatorics, Biweekly Contest 75

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

Hint:

1. Try simulating the entire process.
2. To reduce space, use a temporary array to update nums in every step instead of creating a new array at each step.

[mah-shamim]

We need to find the triangular sum of an array by repeatedly reducing the array until only one element remains. Each reduction step involves creating a new array where each element is the sum of two adjacent elements modulo 10.

Approach

1. Simulation: The problem can be solved by simulating the reduction process step-by-step. We start with the original array and repeatedly compute a new array where each element is the sum of the current element and the next element, modulo 10. This process continues until only one element remains.
2. In-place Update: To optimize space, we can perform the operations in-place. For each reduction step, we update the array from the start, ensuring that each new element is computed and stored in the position of the original array. This avoids the need for creating new arrays at each step, thus saving memory.

Let's implement this solution in PHP: 2221. Find Triangular Sum of an Array

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function triangularSum($nums) {
    $n = count($nums);
    while ($n > 1) {
        for ($i = 0; $i < $n - 1; $i++) {
            $nums[$i] = ($nums[$i] + $nums[$i + 1]) % 10;
        }
        $n--;
    }
    return $nums[0];
}

// Test cases
// Example 1
$nums1 = array(1, 2, 3, 4, 5);
echo "Input: [1,2,3,4,5]\n";
echo "Output: " . triangularSum($nums1) . "\n"; // Expected 8

// Example 2
$nums2 = array(5);
echo "Input: [5]\n";
echo "Output: " . triangularSum($nums2) . "\n"; // Expected 5
?>

Explanation:

1. Initialization: The function starts by determining the length of the input array nums.
2. Reduction Loop: The outer loop continues as long as the effective length of the array ($n) is greater than 1. In each iteration, the inner loop computes the new values for the array by summing adjacent elements and taking modulo 10. The result of each pair is stored back in the array at the position of the first element of the pair.
3. Termination: Once the effective length of the array reduces to 1, the loop terminates, and the first element of the array (which now contains the triangular sum) is returned.

This approach efficiently computes the triangular sum by leveraging in-place updates, ensuring optimal space usage while maintaining clarity and simplicity in the solution. The time complexity is O(n²) due to the nested loops, which is acceptable given the constraints (array length up to 1000).

[basharul-siddike]

Thanks for solving the problem of "Find Triangular Sum of an Array"

[mah-shamim]

Thanks