Program to print Sum Triangle for a given array
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++ 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 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);
}
}
# 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# 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.
<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>
<?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
?>
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.
Recursive Approach: We can obtain the sum triangle using recursion by following the steps given below,
- Base case: If n is 0, just return.
- Create a new array b and store the elements of the given array in it.
- Update the new array b, an element b[i] can be calculated as the sum of b[i] and b[i+1].
- Call the function recursively for the new array b.
- Finally, print the elements of the given array.
Below is the implementation of above approach :
// C++ program to print sum triangle for a given array
#include <bits/stdc++.h>
using namespace std;
// recursive funtion to prints
// sum triangle for arr[0..n-1]
void printTriangle(int arr[], int n)
{
// Base case: if n is 0, just return
if (n == 0)
return;
// Initialize a new array to store
// the given array
int b[n];
for (int i = 0; i < n; i++)
b[i] = arr[i];
// modify the array
for (int i = 0; i < n-1; i++) {
b[i] = b[i] + b[i+1];
}
// recursively calling the function
// for new elements of the array
printTriangle(b,n-1);
// print the given array
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
// Driver Program
int main()
{
int arr[] = { 4, 7, 3, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
printTriangle(arr, n);
return 0;
}
// This code is contributed by abhishekmaran_.
import java.util.Arrays;
public class Main {
// recursive function to print
// sum triangle for arr[0..n-1]
static void printTriangle(int arr[], int n) {
// Base case: if n is 0, just return
if (n == 0)
return;
// Initialize a new array to store
// the given array
int[] b = Arrays.copyOf(arr, n);
// modify the array
for (int i = 0; i < n - 1; i++) {
b[i] = b[i] + b[i + 1];
}
// recursively calling the function
// for new elements of the array
printTriangle(b, n - 1);
// print the given array
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// Driver Program
public static void main(String[] args) {
int[] arr = {4, 7, 3, 6, 7};
int n = arr.length;
printTriangle(arr, n);
}
}
// Function to print sum triangle for a given array
function printTriangle(arr, n) {
// Base case: if n is 0, just return
if (n === 0)
return;
// Initialize a new array to store the given array
let b = arr.slice(0, n);
// Modify the array to calculate the sum triangle
for (let i = 0; i < n - 1; i++) {
b[i] = b[i] + b[i + 1];
}
// Recursively call the function for new elements of the array
printTriangle(b, n - 1);
// Print the given array
console.log(arr.slice(0, n).join(" "));
}
// Driver Program
function main() {
let arr = [4, 7, 3, 6, 7];
let n = arr.length;
printTriangle(arr, n);
}
// Call the main function
main();
# Recursive function to print sum triangle for arr[0..n-1]
def print_triangle(arr, n):
# Base case: if n is 0, just return
if n == 0:
return
# Initialize a new list to store the given array
b = arr[:]
# Modify the array
for i in range(n-1):
b[i] = b[i] + b[i+1]
# Recursively call the function for new elements of the array
print_triangle(b, n-1)
# Print the given array
for i in range(n):
print(arr[i], end=" ")
print()
# Driver Program
if __name__ == "__main__":
arr = [4, 7, 3, 6, 7]
n = len(arr)
print_triangle(arr, n)
Output
81 40 41 21 19 22 11 10 9 13 4 7 3 6 7
Time Complexity: O(n2)
Auxiliary Space: O(n2), there are n recursive calls and for each call we are creating a new array of size n.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above