Given a array, write a program to construct a triangle where last row contains elements of given array, every element of second last row contains sum of below two elements and so on.
Example:
Input: arr[] = {4, 7, 3, 6, 7};
Output:
81
40 41
21 19 22
11 10 9 13
4 7 3 6 7
Input: {10, 40, 50}
Output:
140
50 90
10 40 50
An important observation about output is final value is at the top and top element needs to printed first. Therefore, we use a 2D auxiliary array to construct the triangle in bottom up manner and then print the triangle. An element tri[i][j] of 2D array can be calculated as sum of tri[i+1][j] and tri[i+1][j+1].
Below is the implementation of above idea :
C++
// C++ program to print sum triangle for a given array #include <bits/stdc++.h> using namespace std; // prints sum triangle for arr[0..n-1] void printTriangle(int arr[], int n) { // Initialize a 2D array to store triangle int tri[n][n]; memset(tri, 0, sizeof(tri)); // Initialize last row of triangle for (int i = 0; i < n ; i++) tri[n-1][i] = arr[i]; // Fill other rows for (int i = n-2; i >=0; i--) for (int j = 0; j <= i; j++) tri[i][j] = tri[i+1][j] + tri[i+1][j+1]; // Print the triangle for (int i = 0; i < n; i++) { for(int j = 0; j <= i ; j++) cout << tri[i][j]<<" "; cout << endl; } } // Driver Program int main() { int arr[] = {4, 7, 3, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); printTriangle(arr, n); return 0; } |
Java
// Java program to print sum triangle for a given array class Test{ static int arr[] = new int[]{4, 7, 3, 6, 7}; // prints sum triangle for arr[0..n-1] public static void printTriangle(int n) { // Initialize a 2D array to store triangle int tri[][] = new int[n][n]; // Initialize last row of triangle for (int i = 0; i < n ; i++) tri[n-1][i] = arr[i]; // Fill other rows for (int i = n-2; i >=0; i--) for (int j = 0; j <= i; j++) tri[i][j] = tri[i+1][j] + tri[i+1][j+1]; // Print the triangle for (int i = 0; i < n; i++) { for(int j = 0; j <= i ; j++) System.out.print(tri[i][j] + " "); System.out.println(); } } public static void main(String[] args) { printTriangle(arr.length); } } |
Python3
# Python 3 program to print sum triangle # for a given array # prints sum triangle for arr[0..n-1] def printTriangle(arr, n): # Initialize a 2D array to store triangle tri = [[0 for i in range(n)] for i in range(n)] # Initialize last row of triangle for i in range(n): tri[n - 1][i] = arr[i] # Fill other rows i = n - 2 while(i >= 0): for j in range(0, i + 1, 1): tri[i][j] = (tri[i + 1][j] + tri[i + 1][j + 1]) i -= 1 # Print the triangle for i in range(0, n, 1): for j in range(0, i + 1, 1): print(tri[i][j], end = " ") print("\n", end = "") # Driver Code if __name__ == '__main__': arr = [4, 7, 3, 6, 7] n = len(arr) printTriangle(arr, n) # This code is contributed by # Shashank_Sharma |
C#
// C# program to print sum triangle // for a given array using System; class GFG { static int []arr = new int[]{4, 7, 3, 6, 7}; // prints sum triangle for arr[0..n-1] public static void printTriangle(int n) { // Initialize a 2D array to store triangle int [,]tri = new int[n, n]; // Initialize last row of triangle for (int i = 0; i < n ; i++) tri[n - 1, i] = arr[i]; // Fill other rows for (int i = n - 2; i >= 0; i--) for (int j = 0; j <= i; j++) tri[i, j] = tri[i + 1, j] + tri[i + 1, j + 1]; // Print the triangle for (int i = 0; i < n; i++) { for(int j = 0; j <= i ; j++) Console.Write(tri[i, j] + " "); Console.WriteLine(); } } // Driver Code public static void Main() { printTriangle(arr.Length); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to print sum // triangle for a given array // prints sum triangle for arr[0..n-1] function printTriangle($arr, $n) { // Initialize a 2D array to store triangle $tri[$n][$n] = array(array()); array_fill(0, count($tri), 0); // Initialize last row of triangle for ($i = 0; $i < $n ; $i++) $tri[$n - 1][$i] = $arr[$i]; // Fill other rows for ($i = $n - 2; $i >= 0; $i--) for ($j = 0; $j <= $i; $j++) $tri[$i][$j] = $tri[$i + 1][$j] + $tri[$i + 1][$j + 1]; // Print the triangle for ($i = 0; $i < $n; $i++) { for( $j = 0; $j <= $i ; $j++) echo $tri[$i][$j] . " "; echo "\n"; } } // Driver Code $arr = array(4, 7, 3, 6, 7); $n = count($arr); printTriangle($arr, $n); // This code is contributed by Rajput-Ji ?> |
Javascript
<script> // JavaScript program to print sum triangle for a given array // prints sum triangle for arr[0..n-1] function printTriangle(arr, n) { // Initialize a 2D array to store triangle var tri = new Array(n).fill(0).map((item) => new Array(n).fill(0)); // Initialize last row of triangle for (var i = 0; i < n; i++) tri[n - 1][i] = arr[i]; // Fill other rows for (var i = n - 2; i >= 0; i--) for (var j = 0; j <= i; j++) tri[i][j] = tri[i + 1][j] + tri[i + 1][j + 1]; // Print the triangle for (var i = 0; i < n; i++) { for (var j = 0; j <= i; j++) document.write(tri[i][j] + " "); document.write("<br>"); } } // Driver Program var arr = [4, 7, 3, 6, 7]; var n = arr.length; printTriangle(arr, n); // This code is contributed by rdtank. </script> |
Output:
81 40 41 21 19 22 11 10 9 13 4 7 3 6 7
Time Complexity: O(n2)
Auxiliary Space: O(n2) because using array “tr”
Thanks to nish for suggesting this solution.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
