How to Create Pascal's Triangle in Java
Today, we will learn about the Java Pascal’s triangle. We will learn the three methods: the combination method, arrays, and without using arrays and see these approaches’ time and space complexity.
The Pascal’s Triangle
It is binomial coefficients’ triangular array. It is a triangle of numbers where every number is the sum of two numbers directly above it, excluding the edges that are all 1s.
For instance, the 1+1 = 2 and 1+3 = 4 as highlighted below:
Methods to Write A Program for Pascal’s Triangle in Java
Here, we will be learning about three methods for printing Pascal’s triangle using Java programming.
- Use combination (the combination is a statistical concept) for Java Pascal’s triangle
- Use arrays to print Pascal’s triangle
- Print Pascal’s triangle without using arrays
Let’s dive deeper into every approach listed above.
Use Combination to Print Pascal’s Triangle in Java
Example code:
// pascalTriangle class
public class pascalTriangle {
/*
n number of lines of Pascal's triangle
*/
static void printPascalTriangle(int n) {
for (int line = 0; line < n; line++) {
for (int k = 1; k < n - line; k++) System.out.print(" ");
for (int j = 0; j <= line; j++) System.out.print(nCr(line, j) + " ");
System.out.println();
}
}
// calculates each entry of every line in Pascal's triangle
static int nCr(int n, int r) {
int numerator = 1, denominator = 1;
if (n < r || n == 0)
return 1;
for (int i = r; i >= 1; i--) {
numerator = numerator * n--;
denominator = denominator * i;
}
return (numerator / denominator);
}
// main method
public static void main(String args[]) {
int numberOfLines = 5;
printPascalTriangle(numberOfLines);
}
}
Output:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
We use Combination to print Pascal’s triangle using Java programming. Inside the main method, we get the numberOfLines and pass it to the printPascalTriangle() method to print in a triangular shape.
The printPascalTriangle() method further calls the nCr() method to calculate each entry in every line. Every line number is equal to the number of entries.
For instance, line number 1 has one entry that is 1, line number 2 has two entries that are 1 1, and line number 3 has three entries that are 1 2 1.
Here, every entry is calculated in the nCr() method by using the following formula:
nCr = n! / (r! * (n-r)!)
Here, the nCr is the number of combinations, n is the objects’ total number in a set, and r is the number of selecting objects from a set. The following is the visual demonstration of each entry’s calculation:
By using this method, the time complexity would be O(n3) because we are calling nCr() function for every entry inside the two loops. Remember, the nCr() itself uses a for loop to calculate each entry of every line by using nCr = n! / (r! * (n-r)!) formula.
Can we reduce this time complexity? Yes. We can do that using a 2D array whose solution is given below.
Use Arrays to Print Pascal’s Triangle in Java
If we concentrate on every entry, we can see the sum of two numbers directly above the previous line. All the numbers are zeros outside of the triangle.
For instance, the first row is 0 1 0, where 1 is the part of Pascal’s triangle while 0s are invisible. We can also say that every line of Pascal’s triangle is sandwiched between two zeros.
See the following demonstration:
This makes us think about using a two-dimensional array to calculate, store, and print the values of Pascal’s triangle.
Example code:
public class pascalTriangle {
// calculate all entries of Pascal's triangle
static int[][] calPascalTriangleEntries(int n) {
// create 2D array of n size
int ncrArray[][] = new int[n][n];
// the first entry will always be 1
ncrArray[0][0] = 1;
// starting from the second row
for (int i = 1; i < n; i++) {
// the first entry of each row is always 1
ncrArray[i][0] = 1;
for (int j = 1; j <= i; j++) ncrArray[i][j] = ncrArray[i - 1][j - 1] + ncrArray[i - 1][j];
}
return ncrArray;
}
// print pascal's triangle
static void printPascalTriangle(int pascalEntries[][], int n) {
// prints lines
for (int i = 0; i < n; i++) {
// print spaces
for (int k = 0; k < n - i; k++) System.out.print(" ");
// prints entries
for (int j = 0; j <= i; j++) System.out.print(pascalEntries[i][j] + " ");
System.out.println();
}
}
// main method
public static void main(String[] args) {
int n = 5; // number of lines
int pascalEntries[][] = calPascalTriangleEntries(n);
printPascalTriangle(pascalEntries, n);
}
}
Output:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Here, the main method gets the number of lines and saves it in the n variable, which is passed to the calPascalTriangleEntries() method to calculate the entries of each line of Pascal’s triangle. It returns an array having all entries, which we save in pascalEntries.
Further, we pass pascalEntries and n to the printPascalTriangle() method to print them in a triangular shape. See the output given above.
Here, the time complexity is O(n2). The space complexity is O(n) because we use an additional array.
We can minimize the space complexity using the following solution where we are not using the array.
Print Pascal’s Triangle Without Using Arrays in Java
Example code:
public class pascalTriangle {
public static void main(String[] args) {
int n = 5;
int pascalEntry = 1;
for (int line = 0; line < n; line++) {
// Output the blank space
for (int k = 0; k < n - line; k++) System.out.print(" ");
for (int column = 0; column <= line; column++) {
if (column == 0 || line == column)
pascalEntry = 1;
else
pascalEntry = pascalEntry * (line - column + 1) / column;
System.out.print(pascalEntry + " ");
}
System.out.println();
}
}
}
Output:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
This main method is using the following formula to calculate each entry of every line in Pascal’s triangle:
pascalEntry = pascalEntry * (line - column + 1) / column
This solution is straightforward. We only need to take care of the row (an individual line) and the column index for every pascalEntry within the nested for loop.
Here, the space complexity is O(1), and the time complexity is O(n2).
