Find Triangular Sum of an Array - Practice Coding Problems

Find Triangular Sum of an Array - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4,5]

› Output: 8

💡 Note: Layer by layer: [1,2,3,4,5] → [3,5,7,9] → [8,2,6] → [0,8] → [8]. The triangular sum is 8.

Example 2 — Small Array

$ Input: nums = [5]

› Output: 5

💡 Note: Single element array: the triangular sum is the element itself, which is 5.

Example 3 — Two Elements

$ Input: nums = [7,9]

› Output: 6

💡 Note: Two elements: (7 + 9) % 10 = 16 % 10 = 6. The triangular sum is 6.

Constraints

1 ≤ nums.length ≤ 1000
0 ≤ nums[i] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input Array

Start with array [2,7,4,9] of digits 0-9

Triangular Reduction

Layer by layer: sum adjacent pairs modulo 10 until one element remains

Final Result

The triangular sum is the last remaining element: 4

Key Takeaway

🎯 Key Insight: The triangular sum creates a Pascal's triangle pattern where each element's final contribution follows binomial coefficients

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is recognizing the triangular sum follows Pascal's triangle pattern. The brute force approach simulates layer by layer in O(n²) time. The optimal mathematical approach uses binomial coefficients to calculate directly in O(n) time. Best approach: Mathematical formula with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n²)	O(n²)	Simulate the triangular sum process by creating new arrays layer by layer
Mathematical Formula (Pascal's Triangle)	O(n)	O(1)	Use binomial coefficients to directly calculate the result without simulation
In-Place Simulation	O(n²)	O(1)	Optimize space by reusing the same array instead of creating new ones

Brute Force Simulation — Algorithm Steps

Start with original array
Create new array with sums of adjacent pairs mod 10
Repeat until array has only one element
Return the final element

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Start with input array [2,7,4,9]

Layer 1

Sum adjacent pairs: [(2+7)%10, (7+4)%10, (4+9)%10] = [9,1,3]

Layer 2

Sum adjacent pairs: [(9+1)%10, (1+3)%10] = [0,4]

Final Layer

Sum last pair: [(0+4)%10] = [4]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int* current = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        current[i] = nums[i];
    }
    int currentSize = numsSize;
    
    while (currentSize > 1) {
        int* next = (int*)malloc((currentSize - 1) * sizeof(int));
        for (int i = 0; i < currentSize - 1; i++) {
            next[i] = (current[i] + current[i + 1]) % 10;
        }
        free(current);
        current = next;
        currentSize--;
    }
    
    int result = current[0];
    free(current);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n layers, we process decreasing number of elements: n + (n-1) + ... + 1 = n(n+1)/2

⚠ Quadratic Growth

Space Complexity

O(n²)

We create n arrays with total elements n + (n-1) + ... + 1 = n(n+1)/2

⚠ Quadratic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler