Posted on by Kalkicode
Code Dynamic Programming

# Clark's Triangle

In this article, we will explore Clark's Triangle, a mathematical pattern, and understand how it is generated using a C program. We will discuss the problem statement, the algorithm used to generate the triangle, and the time complexity of the code.

## Introduction

Clark's Triangle is a triangular pattern of numbers named after William B. Clark. The triangle is generated by following a specific set of rules. Each row in the triangle represents the coefficients of a binomial expansion. The elements of the triangle can be calculated using a recursive formula.

## Problem Statement

The problem is to generate Clark's Triangle given two integers, `f` and `m`. The triangle has `m+1` rows, and each row consists of `i+1` elements, where `i` ranges from 0 to `m`. The first element of each row is always 0, and the last element is always 1. The remaining elements are calculated based on the previous row.

## Algorithm

The algorithm for generating Clark's Triangle can be implemented using a dynamic programming approach. Here are the steps:

``````1. Initialize a 2D array dp with dimensions 2 x (m + 1).
2. Set row variable to 0.
3. Iterate from i = 0 to m:
- Set dp[row][0] to i * f.
- Iterate from j = 0 to i:
- If j > 0, calculate the element as follows:
- If j == i, set dp[row][j] to 1 (last element of the row).
- Else if row == 1, set dp[row][j] to dp[0][j] + dp[0][j - 1].
- Else, set dp[row][j] to dp[1][j] + dp[1][j - 1].
- Print the current element.
- Print a new line.
- Update the value of row to alternate between 0 and 1.

4. The generated triangle will be stored in the dp array.``````

## Solution

``````// C Program for
// Clark's Triangle
#include <stdio.h>

void clarkTriangle(int f, int m)
{
if (f <= 0 || m <= 0)
{
return;
}
int dp[2][m + 1];
printf("\n Given f : %d m : %d \n", f, m);
int row = 0;
for (int i = 0; i <= m; ++i)
{
dp[row][0] = i *f;
for (int j = 0; j <= i; ++j)
{
if (j > 0)
{
if (j == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
printf("  %d", dp[row][j]);
}
printf("\n");
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
int main()
{
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
clarkTriangle(6, 10);
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
clarkTriangle(5, 7);
return 0;
}``````

#### Output

`````` Given f : 6 m : 10
0
6  1
12  7  1
18  19  8  1
24  37  27  9  1
30  61  64  36  10  1
36  91  125  100  46  11  1
42  127  216  225  146  57  12  1
48  169  343  441  371  203  69  13  1
54  217  512  784  812  574  272  82  14  1
60  271  729  1296  1596  1386  846  354  96  15  1

Given f : 5 m : 7
0
5  1
10  6  1
15  16  7  1
20  31  23  8  1
25  51  54  31  9  1
30  76  105  85  40  10  1
35  106  181  190  125  50  11  1``````
``````/*
Java program for
Clark's Triangle
*/
public class Triangle
{
public void clarkTriangle(int f, int m)
{
if (f <= 0 || m <= 0)
{
return;
}
int[][] dp = new int[2][m + 1];
System.out.print("\n Given f : " + f + " m : " + m + " \n");
int row = 0;
for (int i = 0; i <= m; ++i)
{
dp[row][0] = i * f;
for (int j = 0; j <= i; ++j)
{
if (j > 0)
{
if (j == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
System.out.print(" " + dp[row][j]);
}
System.out.print("\n");
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
public static void main(String[] args)
{
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
}
}``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program for
Clark's Triangle
*/
class Triangle
{
public: void clarkTriangle(int f, int m)
{
if (f <= 0 || m <= 0)
{
return;
}
int dp[2][m + 1];
cout << "\n Given f : " << f << " m : " << m << " \n";
int row = 0;
for (int i = 0; i <= m; ++i)
{
dp[row][0] = i *f;
for (int j = 0; j <= i; ++j)
{
if (j > 0)
{
if (j == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
cout << " " << dp[row][j];
}
cout << "\n";
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
};
int main()
{
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
return 0;
}``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1``````
``````// Include namespace system
using System;
/*
Csharp program for
Clark's Triangle
*/
public class Triangle
{
public void clarkTriangle(int f, int m)
{
if (f <= 0 || m <= 0)
{
return;
}
int[,] dp = new int[2,m + 1];
Console.Write("\n Given f : " + f + " m : " + m + " \n");
int row = 0;
for (int i = 0; i <= m; ++i)
{
dp[row,0] = i * f;
for (int j = 0; j <= i; ++j)
{
if (j > 0)
{
if (j == i)
{
// When last element
dp[row,j] = 1;
}
else if (row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp[row,j] = dp[0,j] + dp[0,j - 1];
}
else
{
// Combination of top 2 elements
dp[row,j] = dp[1,j] + dp[1,j - 1];
}
}
Console.Write(" " + dp[row,j]);
}
Console.Write("\n");
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
public static void Main(String[] args)
{
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
}
}``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1``````
``````package main
import "fmt"
/*
Go program for
Clark's Triangle
*/

func clarkTriangle(f, m int) {
if f <= 0 || m <= 0 {
return
}
var dp = make([][] int,2)
for i:= 0; i < 2; i++{
dp[i] = make([]int,m + 1);
}
fmt.Print("\n Given f : ", f, " m : ", m, " \n")
var row int = 0
for i := 0 ; i <= m ; i++ {
dp[row][0] = i * f
for j := 0 ; j <= i ; j++ {
if j > 0 {
if j == i {
// When last element
dp[row][j] = 1
} else if row == 1 {
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1]
} else {
// Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1]
}
}
fmt.Print(" ", dp[row][j])
}
fmt.Print("\n")
if row == 1 {
row = 0
} else {
row = 1
}
}
}
func main() {

/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
clarkTriangle(6, 10)
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
clarkTriangle(5, 7)
}``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1``````
``````<?php
/*
Php program for
Clark's Triangle
*/
class Triangle
{
public	function clarkTriangle(\$f, \$m)
{
if (\$f <= 0 || \$m <= 0)
{
return;
}
\$dp = array_fill(0, 2, array_fill(0, \$m + 1, 0));
echo("\n Given f : ".\$f.
" m : ".\$m.
" \n");
\$row = 0;
for (\$i = 0; \$i <= \$m; ++\$i)
{
\$dp[\$row][0] = \$i * \$f;
for (\$j = 0; \$j <= \$i; ++\$j)
{
if (\$j > 0)
{
if (\$j == \$i)
{
// When last element
\$dp[\$row][\$j] = 1;
}
else if (\$row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
\$dp[\$row][\$j] = \$dp[0][\$j] + \$dp[0][\$j - 1];
}
else
{
// Combination of top 2 elements
\$dp[\$row][\$j] = \$dp[1][\$j] + \$dp[1][\$j - 1];
}
}
echo(" ".\$dp[\$row][\$j]);
}
echo("\n");
if (\$row == 1)
{
\$row = 0;
}
else
{
\$row = 1;
}
}
}
}

function main()
{
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
}
main();``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1``````
``````/*
Node JS program for
Clark's Triangle
*/
class Triangle
{
clarkTriangle(f, m)
{
if (f <= 0 || m <= 0)
{
return;
}
var dp = Array(2).fill(0).map(() => new Array(m + 1).fill(0));
process.stdout.write("\n Given f : " + f + " m : " + m + " \n");
var row = 0;
for (var i = 0; i <= m; ++i)
{
dp[row][0] = i * f;
for (var j = 0; j <= i; ++j)
{
if (j > 0)
{
if (j == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
process.stdout.write(" " + dp[row][j]);
}
process.stdout.write("\n");
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}

function main()
{
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
}
main();``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1``````
``````#    Python 3 program for
#    Clark's Triangle
class Triangle :
def clarkTriangle(self, f, m) :
if (f <= 0 or m <= 0) :
return

dp = [[0] * (m + 1) for _ in range(2) ]
print("\n Given f : ", f ," m : ", m ," ")
row = 0
i = 0
while (i <= m) :
dp[row][0] = i * f
j = 0
while (j <= i) :
if (j > 0) :
if (j == i) :
#  When last element
dp[row][j] = 1
elif (row == 1) :
#   Combination of top 2 elements
#   We are using only two rows .
#   And changing the element in first row
#   So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1]
else :
#  Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1]

print(" ", dp[row][j], end = "")
j += 1

print(end = "\n")
if (row == 1) :
row = 0
else :
row = 1

i += 1

def main() :
#    f = 6
#    m = 10
#    ----------------------
#    [0]
#    [6, 1]
#    [12, 7, 1]
#    [18, 19, 8, 1]
#    [24, 37, 27, 9, 1]
#    [30, 61, 64, 36, 10, 1]
#    [36, 91, 125, 100, 46, 11, 1]
#    [42, 127, 216, 225, 146, 57, 12, 1]
#    [48, 169, 343, 441, 371, 203, 69, 13, 1]
#    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
#    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
#    f = 5
#    m = 7
#    ----------------------
#    [0]
#    [5, 1]
#    [10, 6, 1]
#    [15, 16, 7, 1]
#    [20, 31, 23, 8, 1]
#    [25, 51, 54, 31, 9, 1]
#    [30, 76, 105, 85, 40, 10, 1]
#    [35, 106, 181, 190, 125, 50, 11, 1]

if __name__ == "__main__": main()``````

#### Output

`````` Given f :  6  m :  10
0
6  1
12  7  1
18  19  8  1
24  37  27  9  1
30  61  64  36  10  1
36  91  125  100  46  11  1
42  127  216  225  146  57  12  1
48  169  343  441  371  203  69  13  1
54  217  512  784  812  574  272  82  14  1
60  271  729  1296  1596  1386  846  354  96  15  1

Given f :  5  m :  7
0
5  1
10  6  1
15  16  7  1
20  31  23  8  1
25  51  54  31  9  1
30  76  105  85  40  10  1
35  106  181  190  125  50  11  1``````
``````#    Ruby program for
#    Clark's Triangle
class Triangle
def clarkTriangle(f, m)
if (f <= 0 || m <= 0)
return
end

dp = Array.new(2) {Array.new(m + 1) {0}}
print("\n Given f : ", f ," m : ", m ," \n")
row = 0
i = 0
while (i <= m)
dp[row][0] = i * f
j = 0
while (j <= i)
if (j > 0)
if (j == i)
#  When last element
dp[row][j] = 1
elsif (row == 1)
#   Combination of top 2 elements
#   We are using only two rows .
#   And changing the element in first row
#   So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1]
else

#  Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1]
end

end

print(" ", dp[row][j])
j += 1
end

print("\n")
if (row == 1)
row = 0
else

row = 1
end

i += 1
end

end

end

def main()
#    f = 6
#    m = 10
#    ----------------------
#    [0]
#    [6, 1]
#    [12, 7, 1]
#    [18, 19, 8, 1]
#    [24, 37, 27, 9, 1]
#    [30, 61, 64, 36, 10, 1]
#    [36, 91, 125, 100, 46, 11, 1]
#    [42, 127, 216, 225, 146, 57, 12, 1]
#    [48, 169, 343, 441, 371, 203, 69, 13, 1]
#    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
#    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
#    f = 5
#    m = 7
#    ----------------------
#    [0]
#    [5, 1]
#    [10, 6, 1]
#    [15, 16, 7, 1]
#    [20, 31, 23, 8, 1]
#    [25, 51, 54, 31, 9, 1]
#    [30, 76, 105, 85, 40, 10, 1]
#    [35, 106, 181, 190, 125, 50, 11, 1]
end

main()``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1
``````
``````/*
Scala program for
Clark's Triangle
*/
class Triangle()
{
def clarkTriangle(f: Int, m: Int): Unit = {
if (f <= 0 || m <= 0)
{
return;
}
var dp: Array[Array[Int]] = Array.fill[Int](2, m + 1)(0);
print("\n Given f : " + f + " m : " + m + " \n");
var row: Int = 0;
var i: Int = 0;
while (i <= m)
{
dp(row)(0) = i * f;
var j: Int = 0;
while (j <= i)
{
if (j > 0)
{
if (j == i)
{
// When last element
dp(row)(j) = 1;
}
else if (row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp(row)(j) = dp(0)(j) + dp(0)(j - 1);
}
else
{
// Combination of top 2 elements
dp(row)(j) = dp(1)(j) + dp(1)(j - 1);
}
}
print(" " + dp(row)(j));
j += 1;
}
print("\n");
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Triangle = new Triangle();
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
}
}``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1``````
``````/*
Swift 4 program for
Clark's Triangle
*/
class Triangle
{
func clarkTriangle(_ f: Int, _ m: Int)
{
if (f <= 0 || m <= 0)
{
return;
}
var dp: [
[Int]
] = Array(repeating: Array(
repeating: 0, count: m + 1), count: 2);
print("\n Given f : ", f ," m : ", m ," ");
var row: Int = 0;
var i: Int = 0;
while (i <= m)
{
dp[row][0] = i * f;
var j: Int = 0;
while (j <= i)
{
if (j > 0)
{
if (j == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
print(" ", dp[row][j], terminator: "");
j += 1;
}
print(terminator: "\n");
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
func main()
{
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
}
main();``````

#### Output

`````` Given f :  6  m :  10
0
6  1
12  7  1
18  19  8  1
24  37  27  9  1
30  61  64  36  10  1
36  91  125  100  46  11  1
42  127  216  225  146  57  12  1
48  169  343  441  371  203  69  13  1
54  217  512  784  812  574  272  82  14  1
60  271  729  1296  1596  1386  846  354  96  15  1

Given f :  5  m :  7
0
5  1
10  6  1
15  16  7  1
20  31  23  8  1
25  51  54  31  9  1
30  76  105  85  40  10  1
35  106  181  190  125  50  11  1``````
``````/*
Kotlin program for
Clark's Triangle
*/
class Triangle
{
fun clarkTriangle(f: Int, m: Int): Unit
{
if (f <= 0 || m <= 0)
{
return;
}
val dp: Array < Array < Int >> = Array(2)
{
Array(m + 1)
{
0
}
};
print("\n Given f : " + f + " m : " + m + " \n");
var row: Int = 0;
var i: Int = 0;
while (i <= m)
{
dp[row][0] = i * f;
var j: Int = 0;
while (j <= i)
{
if (j > 0)
{
if (j == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
//  Combination of top 2 elements
//  We are using only two rows .
//  And changing the element in first row
//  So get bottom 2 elements.
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Combination of top 2 elements
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
print(" " + dp[row][j]);
j += 1;
}
print("\n");
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
/*
f = 6
m = 10
----------------------
[0]
[6, 1]
[12, 7, 1]
[18, 19, 8, 1]
[24, 37, 27, 9, 1]
[30, 61, 64, 36, 10, 1]
[36, 91, 125, 100, 46, 11, 1]
[42, 127, 216, 225, 146, 57, 12, 1]
[48, 169, 343, 441, 371, 203, 69, 13, 1]
[54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
[60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
*/
/*
f = 5
m = 7
----------------------
[0]
[5, 1]
[10, 6, 1]
[15, 16, 7, 1]
[20, 31, 23, 8, 1]
[25, 51, 54, 31, 9, 1]
[30, 76, 105, 85, 40, 10, 1]
[35, 106, 181, 190, 125, 50, 11, 1]
*/
}``````

#### Output

`````` Given f : 6 m : 10
0
6 1
12 7 1
18 19 8 1
24 37 27 9 1
30 61 64 36 10 1
36 91 125 100 46 11 1
42 127 216 225 146 57 12 1
48 169 343 441 371 203 69 13 1
54 217 512 784 812 574 272 82 14 1
60 271 729 1296 1596 1386 846 354 96 15 1

Given f : 5 m : 7
0
5 1
10 6 1
15 16 7 1
20 31 23 8 1
25 51 54 31 9 1
30 76 105 85 40 10 1
35 106 181 190 125 50 11 1``````

## Time Complexity

The time complexity of the algorithm is `O(m^2)`. The outer loop iterates `m` times, and the inner loop also iterates up to `m` times. Therefore, the overall time complexity is quadratic in terms of the input size.

## Comment

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.

Categories
Relative Post