Pascal’s Triangle: flowchart, algorithm and program
This program reads n and prints the first n rows of Pascal's triangle as a centered pyramid. Instead of using factorials or an array, it builds each number in a row from the one before it using a simple multiply-and-divide step.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read n.
- Step 3: Set i = 0.
- Step 4: If i < n, go to step 5; otherwise go to step 16.
- Step 5: Set k = 0.
- Step 6: If k < n - i - 1, go to step 7; otherwise go to step 9.
- Step 7: Print space.
- Step 8: Set k = k + 1. Go to step 6.
- Step 9: Set value = 1, j = 0.
- Step 10: If j <= i, go to step 11; otherwise go to step 14.
- Step 11: Print value.
- Step 12: Set value = value * (i - j) / (j + 1).
- Step 13: Set j = j + 1. Go to step 10.
- Step 14: Print newline.
- Step 15: Set i = i + 1. Go to step 4.
- Step 16: Stop.
Pseudocode
BEGIN
READ n
i ← 0
WHILE i < n DO
k ← 0
WHILE k < n - i - 1 DO
PRINT space
k ← k + 1
END WHILE
value ← 1, j ← 0
WHILE j <= i DO
PRINT value
value ← value * (i - j) / (j + 1)
j ← j + 1
END WHILE
PRINT newline
i ← i + 1
END WHILE
END
Program in C, Python and Java
Pascal’s Triangle program in C
#include <stdio.h>
int main() {
int n, i, j, k, value;
printf("Enter n: ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
for (k = 0; k < n - i - 1; k++) {
printf(" ");
}
value = 1;
for (j = 0; j <= i; j++) {
printf("%d ", value);
value = value * (i - j) / (j + 1);
}
printf("\n");
}
return 0;
}Pascal’s Triangle program in Python
n = int(input("Enter n: "))
for i in range(n):
print(" " * (n - i - 1), end="")
value = 1
for j in range(i + 1):
print(value, end=" ")
value = value * (i - j) // (j + 1)
print()Pascal’s Triangle program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
for (int k = 0; k < n - i - 1; k++) {
System.out.print(" ");
}
int value = 1;
for (int j = 0; j <= i; j++) {
System.out.print(value + " ");
value = value * (i - j) / (j + 1);
}
System.out.println();
}
}
}
Sample input: n = 5
Output: 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
How it works
- The outer loop on i runs once per row, from 0 to n - 1. Row i has i + 1 numbers.
- The loop on k prints n - i - 1 spaces first, so the rows shift right by less each time and the output looks like a triangle.
- Each row starts with value = 1, because the first number in every row is always 1.
- Inside the loop on j, the program prints value and then updates it with value = value * (i - j) / (j + 1). This turns C(i, j) into C(i, j + 1), the next number in the row.
- For row i = 4: value goes 1 -> 1*4/1 = 4 -> 4*3/2 = 6 -> 6*2/3 = 4 -> 4*1/4 = 1, which gives 1 4 6 4 1.
- A newline is printed after each row, and the next row starts with value reset to 1.
Dry run (trace table)
| Step | Line | Box | n | i | k | value | j | Output |
|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||||
| 2 | 6 | Read n | 5 | Enter n: | ||||
| 3 | 7 | i = 0 | 5 | 0 | ||||
| 4 | 7 | i < n? | 5 | 0 | ||||
| 5 | 8 | k = 0 | 5 | 0 | 0 | |||
| 6 | 8 | k < n - i - 1? | 5 | 0 | 0 | |||
| 7 | 9 | Print space | 5 | 0 | 0 | |||
| 8 | 8 | k = k + 1 | 5 | 0 | 1 | |||
| 9 | 8 | k < n - i - 1? | 5 | 0 | 1 | |||
| 10 | 9 | Print space | 5 | 0 | 1 | |||
| 11 | 8 | k = k + 1 | 5 | 0 | 2 | |||
| 12 | 8 | k < n - i - 1? | 5 | 0 | 2 | |||
| 13 | 9 | Print space | 5 | 0 | 2 | |||
| 14 | 8 | k = k + 1 | 5 | 0 | 3 | |||
| 15 | 8 | k < n - i - 1? | 5 | 0 | 3 | |||
| 16 | 9 | Print space | 5 | 0 | 3 | |||
| 17 | 8 | k = k + 1 | 5 | 0 | 4 | |||
| 18 | 8 | k < n - i - 1? | 5 | 0 | 4 | |||
| 19 | 11 | value = 1, j = 0 | 5 | 0 | 4 | 1 | 0 | |
| 20 | 12 | j <= i? | 5 | 0 | 4 | 1 | 0 |
Time and space complexity
Time: O(n²) · Space: O(1). Each of the n rows runs inner loops of at most n iterations with constant work, and only a few variables are stored.
Common mistakes
- Writing value = value / (j + 1) * (i - j). Integer division then truncates too early and gives wrong numbers in the middle of the row.
- Forgetting to reset value = 1 at the start of each row, so the next row begins with a leftover number.
- Getting the space count wrong (for example n - i instead of n - i - 1), which shifts the whole triangle out of alignment.
Viva questions
Q1. Why is value set to 1 at line 11, and why is it done inside the outer loop?
The first entry of every row in Pascal's triangle is C(i,0) = 1. It is reset for each row because after the last entry of the previous row value would be 0, so every row needs to start fresh at 1.
Q2. What does the loop at lines 8-10 do, and why does it run n - i - 1 times?
It prints leading spaces to push the row to the right so the triangle looks centred. Row 0 needs the most spaces (n-1) and the last row needs none, so the count decreases by one with each row.
Q3. Explain the formula value = value * (i - j) / (j + 1). What does it compute?
It computes the next binomial coefficient in row i from the current one: C(i,j+1) = C(i,j) * (i-j) / (j+1). So each entry is built from the previous entry without needing the previous row or factorials.
Q4. Why is the multiplication done before the division? What would go wrong if you wrote value * ((i-j)/(j+1))?
Integer division truncates. Multiplying first gives value*(i-j), which is exactly divisible by (j+1), so the result is exact. Dividing (i-j)/(j+1) first would often give 0 or a truncated number and the entries would be wrong.
Q5. What is the value of value after the last iteration of the inner loop, and is anything wrong with computing it?
When j = i, the factor (i-j) is 0, so value becomes 0. That value is never printed, so it is harmless, just one extra calculation.
Q6. What does the program print for n = 0, n = 1, and a negative n?
For n = 0 or a negative n, the outer loop condition i < n is false immediately, so nothing is printed. For n = 1 it prints just '1 ' on one line with no leading spaces.
Q7. What is the time complexity of this program?
The outer loop runs n times and the inner loop runs i+1 times, so total work is 1+2+...+n = n(n+1)/2, which is O(n^2). The space used is O(1) because only a few variables are stored.
Q8. What would change if n were large, say 20 or more, or if you wanted to use a different method?
With int, value * (i-j) can overflow for large rows (roughly beyond n = 17 or so), giving wrong numbers; using long long or unsigned long long delays this. Alternatively you could store the previous row in an array and add adjacent elements, which avoids multiplication and division.
Frequently asked questions
Why does value = value * (i - j) / (j + 1) give the next number in the row?
Each entry is a binomial coefficient, and C(i, j + 1) = C(i, j) * (i - j) / (j + 1). So the next value comes straight from the previous one with no factorials needed.
Why multiply before dividing instead of the other way around?
With integer division, dividing first would drop the fractional part and give wrong results. value * (i - j) is always exactly divisible by (j + 1), so multiplying first keeps the answer exact.
What is the time complexity of this program?
It is O(n^2), since row i prints i + 1 numbers and the total is 1 + 2 + ... + n. It needs only O(1) extra space because no array is stored.