Display Trinomial triangle
The Trinomial Triangle is a triangular pattern of numbers that represents the coefficients of the expansion of (1 + x + x^2)^n. Each number in the triangle is the sum of the three numbers directly above it in the row above. The triangle starts with a row containing only 1 and continues to expand as per the given size. It has applications in various mathematical and combinatorial problems.
Problem Statement:
The problem is to display the Trinomial Triangle with a given size. The size represents the number of rows in the triangle. We need to generate the Trinomial Triangle and print it in a triangular format.
Example:
Let's consider the case of size 5.
ROW SIZE : 5
1 1 1 1 1 2 3 2 1 1 3 6 7 6 3 1 1 4 10 16 19 16 10 4 1
In the above example, the Trinomial Triangle with size 5 is displayed. Each number represents the coefficient of the respective term in the expansion of (1 + x + x^2)^n.
Algorithm:
1. Define a function sum_result(result[], row, col, size)
that takes the resultant array, current row, current column, and size as inputs and returns the sum of the three numbers directly above the current position.
2. Define a function show(result[], size)
that takes the resultant array and size as inputs and displays the Trinomial Triangle in a triangular format.
3. Define a function set_default(result[], size)
that sets the default value of the resultant array to 0.
4. Define a function trinomial_triangle(size)
that takes the size as input and generates the Trinomial Triangle.
5. Inside the trinomial_triangle
function, calculate the capacity of the resultant array based on the size.
6. Declare and initialize the resultant array with default values using the set_default
function.
7. Set the first row element of the resultant array to 1.
8. Iterate from the second row to the given size.
9. Calculate the number of valid operations in the current row using a counter variable.
10. Update the column value for the current row.
11. Iterate over the valid operations in the current row and calculate the sum of the three numbers directly above the current position using the sum_result
function.
12. Store the calculated sum in the resultant array at the current position.
13. Display the Trinomial Triangle using the show
function.
14. Call the trinomial_triangle
function with different sizes to test the code.
Pseudocode:
sum_result(result[], row, col, size):
ans = 0
if row >= 0 and row < size and col >= 0 and col < (size * 2):
if col - 1 >= 0:
ans += result[(row) * (size * 2) + (col - 1)]
ans += result[(row) * (size * 2) + (col)]
if col + 1 < (size * 2):
ans += result[(row) * (size * 2) + (col + 1)]
return ans
show(result[], size):
for i from 0 to size-1:
for j from 0 to size*2-1:
if result[(i * (size * 2)) + j] != 0:
print result[(i * (size * 2)) + j]
else if j != 0:
print " "
print new line
set_default(result[], size):
for i from 0 to size-1:
result[i] = 0
trinomial_triangle(size):
print "ROW SIZE: ", size
capacity = size * (size * 2)
result[capacity]
col = (size * 2) / 2
counter = 1
set_default(result, capacity)
result[col] = 1
for i from 1 to size-1:
counter = counter + 2
col = col - 1
for j from 0 to counter-1 and j + col < size * 2:
result[(i * (size * 2)) + col + j] = sum_result(result, i - 1, col + j, size)
show(result, size)
main():
trinomial_triangle(5)
trinomial_triangle(7)
Code Solution
Here given code implementation process.
//C Program
//Display Trinomial triangle
#include <stdio.h>
#include <stdlib.h>
int sum_result(int result[], int row, int col, int size)
{
int ans = 0;
//Check boundary condition
if (row >= 0 && row < size && col >= 0 && col < (size * 2))
{
if (col - 1 >= 0)
{
//When fill result column is greater than zero
ans += result[(row) * (size * 2) + (col - 1)];
}
//get the result of just above element of resultant matrix
ans += result[(row) * (size * 2) + (col)];
if (col + 1 < (size * 2))
{
ans += result[(row) * (size * 2) + (col + 1)];
}
}
return ans;
}
//Display result of trinomial triangle
void show(int result[], int size)
{
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < size * 2; ++j)
{
if (result[(i * (size * 2)) + j] != 0)
{
printf("%d\t", result[(i * (size * 2)) + j]);
}
else if (j != 0)
{
printf("\t");
}
}
printf("\n");
}
}
//Set default value of resultant array
void set_default(int result[], int size)
{
for (int i = 0; i < size; ++i)
{
result[i] = 0;
}
}
void trinomial_triangle(int size)
{
printf("\n ROW SIZE : %d\n", size);
// Number of spaces are required to store trinomial triangle element
int capacity = size * (size * 2);
// Used to store result of trinomial triangle
int result[capacity];
int col = (size * 2) / 2;
int counter = 1;
set_default(result, capacity);
//Set the first row element
result[col] = 1;
for (int i = 1; i < size; ++i)
{
//This is indicate number of valid operation in i-th row
counter = counter + 2;
col = col - 1;
for (int j = 0; j < counter && j + col < size * 2; ++j)
{
//Store the result of top three closest element
result[(i * (size * 2)) + col + j] = sum_result(result, i - 1, col + j, size);
}
}
show(result, size);
}
int main()
{
//Test Cases
trinomial_triangle(5);
trinomial_triangle(7);
return 0;
}
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
// Java Program
// Display Trinomial Triangle
class MyPattern
{
public int sum_result(int[] result, int row, int col, int size)
{
int ans = 0;
//Check boundary condition
if (row >= 0 && row < size && col >= 0 && col < (size * 2))
{
if (col - 1 >= 0)
{
//When fill result column is greater than zero
ans += result[(row) * (size * 2) + (col - 1)];
}
//get the result of just above element of resultant matrix
ans += result[(row) * (size * 2) + (col)];
if (col + 1 < (size * 2))
{
ans += result[(row) * (size * 2) + (col + 1)];
}
}
return ans;
}
//Display result of trinomial triangle
public void show(int[] result, int size)
{
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < size * 2; ++j)
{
if (result[(i * (size * 2)) + j] != 0)
{
System.out.print("" + result[(i * (size * 2)) + j] + "\t");
}
else if (j != 0)
{
System.out.print("\t");
}
}
System.out.print("\n");
}
}
//Set default value of resultant array
public void set_default(int[] result, int size)
{
for (int i = 0; i < size; ++i)
{
result[i] = 0;
}
}
public void trinomial_triangle(int size)
{
System.out.print("\n ROW SIZE : " + size + "\n");
// Number of spaces are required to store trinomial triangle element
int capacity = size * (size * 2);
// Used to store result of trinomial triangle
int[] result = new int[capacity];
int col = (size * 2) / 2;
int counter = 1;
set_default(result, capacity);
//Set the first row element
result[col] = 1;
for (int i = 1; i < size; ++i)
{
//This is indicate number of valid operation in i-th row
counter = counter + 2;
col = col - 1;
for (int j = 0; j < counter && j + col < size * 2; ++j)
{
//Store the result of top three closest element
result[(i * (size * 2)) + col + j] = sum_result(result, i - 1, col + j, size);
}
}
show(result, size);
}
public static void main(String[] args)
{
MyPattern obj = new MyPattern();
//Test Cases
obj.trinomial_triangle(5);
obj.trinomial_triangle(7);
}
}
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
// C++ Program
// Display Trinomial Triangle
#include<iostream>
using namespace std;
class MyPattern
{
public: int sum_result(int result[], int row, int col, int size)
{
int ans = 0;
//Check boundary condition
if (row >= 0 && row < size && col >= 0 && col < (size *2))
{
if (col - 1 >= 0)
{
//When fill result column is greater than zero
ans += result[(row) *(size *2) + (col - 1)];
}
//get the result of just above element of resultant matrix
ans += result[(row) *(size *2) + (col)];
if (col + 1 < (size *2))
{
ans += result[(row) *(size *2) + (col + 1)];
}
}
return ans;
}
//Display result of trinomial triangle
void show(int result[], int size)
{
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < size *2; ++j)
{
if (result[(i *(size *2)) + j] != 0)
{
cout << "" << result[(i *(size *2)) + j] << "\t";
}
else if (j != 0)
{
cout << "\t";
}
}
cout << "\n";
}
}
//Set default value of resultant array
void set_default(int result[], int size)
{
for (int i = 0; i < size; ++i)
{
result[i] = 0;
}
}
void trinomial_triangle(int size)
{
cout << "\n ROW SIZE : " << size << "\n";
// Number of spaces are required to store trinomial triangle element
int capacity = size *(size *2);
int *result = new int[capacity];
int col = (size *2) / 2;
int counter = 1;
this->set_default(result, capacity);
//Set the first row element
result[col] = 1;
for (int i = 1; i < size; ++i)
{
//This is indicate number of valid operation in i-th row
counter = counter + 2;
col = col - 1;
for (int j = 0; j < counter && j + col < size *2; ++j)
{
//Store the result of top three closest element
result[(i *(size *2)) + col + j] = this->sum_result(result, i - 1, col + j, size);
}
}
this->show(result, size);
}
};
int main()
{
MyPattern obj = MyPattern();
//Test Cases
obj.trinomial_triangle(5);
obj.trinomial_triangle(7);
return 0;
}
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
// C# Program
// Display Trinomial Triangle
using System;
class MyPattern
{
public int sum_result(int[] result, int row, int col, int size)
{
int ans = 0;
//Check boundary condition
if (row >= 0 && row < size && col >= 0 && col < (size * 2))
{
if (col - 1 >= 0)
{
//When fill result column is greater than zero
ans += result[(row) * (size * 2) + (col - 1)];
}
//get the result of just above element of resultant matrix
ans += result[(row) * (size * 2) + (col)];
if (col + 1 < (size * 2))
{
ans += result[(row) * (size * 2) + (col + 1)];
}
}
return ans;
}
//Display result of trinomial triangle
public void show(int[] result, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size * 2; j++)
{
if (result[(i * (size * 2)) + j] != 0)
{
Console.Write("" + result[(i * (size * 2)) + j] + "\t");
}
else if (j != 0)
{
Console.Write("\t");
}
}
Console.Write("\n");
}
}
//Set default value of resultant array
public void set_default(int[] result, int size)
{
for (int i = 0; i < size; i++)
{
result[i] = 0;
}
}
public void trinomial_triangle(int size)
{
Console.Write("\n ROW SIZE : " + size + "\n");
// Number of spaces are required to store trinomial triangle element
int capacity = size * (size * 2);
int[] result = new int[capacity];
int col = (size * 2) / 2;
int counter = 1;
set_default(result, capacity);
//Set the first row element
result[col] = 1;
for (int i = 1; i < size; i++)
{
//This is indicate number of valid operation in i-th row
counter = counter + 2;
col = col - 1;
for (int j = 0; j < counter && j + col < size * 2; j++)
{
//Store the result of top three closest element
result[(i * (size * 2)) + col + j] = sum_result(result, i - 1, col + j, size);
}
}
show(result, size);
}
public static void Main(String[] args)
{
MyPattern obj = new MyPattern();
//Test Cases
obj.trinomial_triangle(5);
obj.trinomial_triangle(7);
}
}
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
<?php
// Php Program
// Display Trinomial Triangle
class MyPattern
{
public function sum_result( & $result, $row, $col, $size)
{
$ans = 0;
//Check boundary condition
if ($row >= 0 && $row < $size && $col >= 0 && $col < ($size *2))
{
if ($col - 1 >= 0)
{
//When fill result column is greater than zero
$ans += $result[($row) *($size *2) + ($col - 1)];
}
//get the result of just above element of resultant matrix
$ans += $result[($row) *($size *2) + ($col)];
if ($col + 1 < ($size *2))
{
$ans += $result[($row) *($size *2) + ($col + 1)];
}
}
return $ans;
}
//Display result of trinomial triangle
public function show( & $result, $size)
{
for ($i = 0; $i < $size; ++$i)
{
for ($j = 0; $j < $size *2; ++$j)
{
if ($result[($i *($size *2)) + $j] != 0)
{
echo("". $result[($i *($size *2)) + $j] ."\t");
}
else if ($j != 0)
{
echo("\t");
}
}
echo("\n");
}
}
//Set default value of resultant array
public function set_default( & $result, $size)
{
for ($i = 0; $i < $size; ++$i)
{
$result[$i] = 0;
}
}
public function trinomial_triangle($size)
{
echo("\n ROW SIZE : ". $size ."\n");
// Number of spaces are required to store trinomial triangle element
$capacity = $size *($size *2);
// Used to store result of trinomial triangle
$result = array_fill(0, $capacity, 0);
$col = intval(($size *2) / 2);
$counter = 1;
$this->set_default($result, $capacity);
//Set the first row element
$result[$col] = 1;
for ($i = 1; $i < $size; ++$i)
{
//This is indicate number of valid operation in i-th row
$counter = $counter + 2;
$col = $col - 1;
for ($j = 0; $j < $counter && $j + $col < $size *2; ++$j)
{
//Store the result of top three closest element
$result[($i *($size *2)) + $col + $j] = $this->sum_result($result, $i - 1, $col + $j, $size);
}
}
$this->show($result, $size);
}
}
function main()
{
$obj = new MyPattern();
//Test Cases
$obj->trinomial_triangle(5);
$obj->trinomial_triangle(7);
}
main();
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
// Node Js Program
// Display Trinomial Triangle
class MyPattern
{
sum_result(result, row, col, size)
{
var ans = 0;
//Check boundary condition
if (row >= 0 && row < size && col >= 0 && col < (size *2))
{
if (col - 1 >= 0)
{
//When fill result column is greater than zero
ans += result[(row) *(size *2) + (col - 1)];
}
//get the result of just above element of resultant matrix
ans += result[(row) *(size *2) + (col)];
if (col + 1 < (size *2))
{
ans += result[(row) *(size *2) + (col + 1)];
}
}
return ans;
}
//Display result of trinomial triangle
show(result, size)
{
for (var i = 0; i < size; ++i)
{
for (var j = 0; j < size *2; ++j)
{
if (result[(i *(size *2)) + j] != 0)
{
process.stdout.write("" + result[(i *(size *2)) + j] + "\t");
}
else if (j != 0)
{
process.stdout.write("\t");
}
}
process.stdout.write("\n");
}
}
//Set default value of resultant array
set_default(result, size)
{
for (var i = 0; i < size; ++i)
{
result[i] = 0;
}
}
trinomial_triangle(size)
{
process.stdout.write("\n ROW SIZE : " + size + "\n");
// Number of spaces are required to store trinomial triangle element
var capacity = size *(size *2);
// Used to store result of trinomial triangle
var result = Array(capacity).fill(0);
var col = parseInt((size *2) / 2);
var counter = 1;
this.set_default(result, capacity);
//Set the first row element
result[col] = 1;
for (var i = 1; i < size; ++i)
{
//This is indicate number of valid operation in i-th row
counter = counter + 2;
col = col - 1;
for (var j = 0; j < counter && j + col < size *2; ++j)
{
//Store the result of top three closest element
result[(i *(size *2)) + col + j] = this.sum_result(result, i - 1, col + j, size);
}
}
this.show(result, size);
}
}
function main(args)
{
var obj = new MyPattern();
//Test Cases
obj.trinomial_triangle(5);
obj.trinomial_triangle(7);
}
main();
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
# Python 3 Program
# Display Trinomial Triangle
class MyPattern :
def sum_result(self, result, row, col, size) :
ans = 0
# Check boundary condition
if (row >= 0 and row < size and col >= 0 and col < (size * 2)) :
if (col - 1 >= 0) :
# When fill result column is greater than zero
ans += result[(row) * (size * 2) + (col - 1)]
# get the result of just above element of resultant matrix
ans += result[(row) * (size * 2) + (col)]
if (col + 1 < (size * 2)) :
ans += result[(row) * (size * 2) + (col + 1)]
return ans
# Display result of trinomial triangle
def show(self, result, size) :
i = 0
j = 0
while (i < size) :
j = 0
while (j < size * 2) :
if (result[(i * (size * 2)) + j] != 0) :
print("", result[(i * (size * 2)) + j] ,"\t", end = "")
elif (j != 0) :
print("\t", end = "")
j += 1
print("\n", end = "")
i += 1
# Set default value of resultant array
def set_default(self, result, size) :
i = 0
while (i < size) :
result[i] = 0
i += 1
def trinomial_triangle(self, size) :
print("\n ROW SIZE : ", size ,"\n", end = "")
# Number of spaces are required to store trinomial triangle element
capacity = size * (size * 2)
result = [0] * capacity
col = int((size * 2) / 2)
counter = 1
self.set_default(result, capacity)
# Set the first row element
result[col] = 1
i = 1
while (i < size) :
# This is indicate number of valid operation in i-th row
counter = counter + 2
col = col - 1
j = 0
while (j < counter and j + col < size * 2) :
# Store the result of top three closest element
result[(i * (size * 2)) + col + j] = self.sum_result(result, i - 1, col + j, size)
j += 1
i += 1
self.show(result, size)
def main() :
obj = MyPattern()
# Test Cases
obj.trinomial_triangle(5)
obj.trinomial_triangle(7)
if __name__ == "__main__": main()
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
# Ruby Program
# Display Trinomial Triangle
class MyPattern
def sum_result(result, row, col, size)
ans = 0
# Check boundary condition
if (row >= 0 && row < size && col >= 0 && col < (size * 2))
if (col - 1 >= 0)
# When fill result column is greater than zero
ans += result[(row) * (size * 2) + (col - 1)]
end
# get the result of just above element of resultant matrix
ans += result[(row) * (size * 2) + (col)]
if (col + 1 < (size * 2))
ans += result[(row) * (size * 2) + (col + 1)]
end
end
return ans
end
# Display result of trinomial triangle
def show(result, size)
i = 0
j = 0
while (i < size)
j = 0
while (j < size * 2)
if (result[(i * (size * 2)) + j] != 0)
print("", result[(i * (size * 2)) + j] ,"\t")
elsif (j != 0)
print("\t")
end
j += 1
end
print("\n")
i += 1
end
end
# Set default value of resultant array
def set_default(result, size)
i = 0
while (i < size)
result[i] = 0
i += 1
end
end
def trinomial_triangle(size)
print("\n ROW SIZE :", size ,"\n")
# Number of spaces are required to store trinomial triangle element
capacity = size * (size * 2)
result = Array.new(capacity) {0}
col = (size * 2) / 2
counter = 1
self.set_default(result, capacity)
# Set the first row element
result[col] = 1
i = 1
while (i < size)
# This is indicate number of valid operation in i-th row
counter = counter + 2
col = col - 1
j = 0
while (j < counter && j + col < size * 2)
# Store the result of top three closest element
result[(i * (size * 2)) + col + j] = self.sum_result(result, i - 1, col + j, size)
j += 1
end
i += 1
end
self.show(result, size)
end
end
def main()
obj = MyPattern.new()
# Test Cases
obj.trinomial_triangle(5)
obj.trinomial_triangle(7)
end
main()
Output
ROW SIZE :5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE :7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
// Scala Program
// Display Trinomial Triangle
class MyPattern
{
def sum_result(result: Array[Int], row: Int, col: Int, size: Int): Int = {
var ans: Int = 0;
//Check boundary condition
if (row >= 0 && row < size && col >= 0 && col < (size * 2))
{
if (col - 1 >= 0)
{
//When fill result column is greater than zero
ans += result((row) * (size * 2) + (col - 1));
}
//get the result of just above element of resultant matrix
ans += result((row) * (size * 2) + (col));
if (col + 1 < (size * 2))
{
ans += result((row) * (size * 2) + (col + 1));
}
}
return ans;
}
//Display result of trinomial triangle
def show(result: Array[Int], size: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
while (i < size)
{
j = 0;
while (j < size * 2)
{
if (result((i * (size * 2)) + j) != 0)
{
print("" + result((i * (size * 2)) + j) + "\t");
}
else if (j != 0)
{
print("\t");
}
j += 1;
}
print("\n");
i += 1;
}
}
//Set default value of resultant array
def set_default(result: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
result(i) = 0;
i += 1;
}
}
def trinomial_triangle(size: Int): Unit = {
print("\n ROW SIZE : " + size + "\n");
// Number of spaces are required to store trinomial triangle element
var capacity: Int = size * (size * 2);
var result: Array[Int] = Array.fill[Int](capacity)(0);
var col: Int = ((size * 2) / 2).toInt;
var counter: Int = 1;
set_default(result, capacity);
//Set the first row element
result(col) = 1;
var i: Int = 1;
while (i < size)
{
//This is indicate number of valid operation in i-th row
counter = counter + 2;
col = col - 1;
var j: Int = 0;
while (j < counter && j + col < size * 2)
{
//Store the result of top three closest element
result((i * (size * 2)) + col + j) = sum_result(result, i - 1, col + j, size);
j += 1;
}
i += 1;
}
show(result, size);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyPattern = new MyPattern();
//Test Cases
obj.trinomial_triangle(5);
obj.trinomial_triangle(7);
}
}
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
// Swift Program
// Display Trinomial Triangle
class MyPattern
{
func sum_result(_ result: [Int], _ row: Int, _ col: Int, _ size: Int) -> Int
{
var ans: Int = 0;
//Check boundary condition
if (row >= 0 && row < size && col >= 0 && col < (size * 2))
{
if (col - 1 >= 0)
{
//When fill result column is greater than zero
ans += result[(row) * (size * 2) + (col - 1)];
}
//get the result of just above element of resultant matrix
ans += result[(row) * (size * 2) + (col)];
if (col + 1 < (size * 2))
{
ans += result[(row) * (size * 2) + (col + 1)];
}
}
return ans;
}
//Display result of trinomial triangle
func show(_ result: [Int], _ size: Int)
{
var i: Int = 0;
var j: Int = 0;
while (i < size)
{
j = 0;
while (j < size * 2)
{
if (result[(i * (size * 2)) + j] != 0)
{
print("", result[(i * (size * 2)) + j] ,"\t", terminator: "");
}
else if (j != 0)
{
print("\t", terminator: "");
}
j += 1;
}
print("\n", terminator: "");
i += 1;
}
}
//Set default value of resultant array
func set_default(_ result: inout[Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
result[i] = 0;
i += 1;
}
}
func trinomial_triangle(_ size: Int)
{
print("\n ROW SIZE : ", size ,"\n", terminator: "");
// Number of spaces are required to store trinomial triangle element
let capacity: Int = size * (size * 2);
var result: [Int] = Array(repeating: 0, count: capacity);
var col: Int = (size * 2) / 2;
var counter: Int = 1;
self.set_default(&result, capacity);
//Set the first row element
result[col] = 1;
var i: Int = 1;
while (i < size)
{
//This is indicate number of valid operation in i-th row
counter = counter + 2;
col = col - 1;
var j: Int = 0;
while (j < counter && j + col < size * 2)
{
//Store the result of top three closest element
result[(i * (size * 2)) + col + j] = self.sum_result(result, i - 1, col + j, size);
j += 1;
}
i += 1;
}
self.show(result, size);
}
}
func main()
{
let obj: MyPattern = MyPattern();
//Test Cases
obj.trinomial_triangle(5);
obj.trinomial_triangle(7);
}
main();
Output
ROW SIZE : 5
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
ROW SIZE : 7
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
Time Complexity:
The time complexity of the given code is O(size^2), where size represents the number of rows in the Trinomial Triangle. The nested loops iterate over each element in the triangle, and the number of elements is proportional to the square of the size.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment