Pascal’s Triangle using Binomial Coefficient
The number of entries in every line is equal to line number. For example, the first line has “1“, the second line has “1 1“, the third line has “1 2 1“,.. and so on. Every entry in a line is value of a Binomial Coefficient. The value of ith entry in line number line is C(line, i). The value can be calculated using following formula.
- C(line, i) = line! / ( (line-i)! * i! )
Algorithm:
- Run a loop for each row of pascal’s triangle i.e. 1 to N.
- For each row, run an internal loop for each element of that row.
- Calculate the binomial coefficient for the element using the formula mentioned in the approach.
- For each row, run an internal loop for each element of that row.
Below is the implementation of the above approach:
C++
// C++ code for Pascal's Triangle#include <iostream>using namespace std;int binomialCoeff(int n, int k);// Function to print first// n lines of Pascal's// Trianglevoid printPascal(int n){ // Iterate through every line and // print entries in it for (int line = 0; line < n; line++) { // Every line has number of // integers equal to line // number for (int i = 0; i <= line; i++) cout << " " << binomialCoeff(line, i); cout << "\n"; }}// See// for details of this functionint binomialCoeff(int n, int k){ int res = 1; if (k > n - k) k = n - k; for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// Driver programint main(){ int n = 7; printPascal(n); return 0;}// This code is contributed by shivanisinghss2110 |
C
// C++ code for Pascal's Triangle#include <stdio.h>// for details of this functionint binomialCoeff(int n, int k);// Function to print first// n lines of Pascal's // Trianglevoid printPascal(int n){ // Iterate through every line and // print entries in it for (int line = 0; line < n; line++) { // Every line has number of // integers equal to line // number for (int i = 0; i <= line; i++) printf("%d ", binomialCoeff(line, i)); printf("\n"); }}// for details of this functionint binomialCoeff(int n, int k){ int res = 1; if (k > n - k) k = n - k; for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// Driver program int main(){ int n = 7; printPascal(n); return 0;} |
Java
// Java code for Pascal's Triangleimport java.io.*;class GFG { // Function to print first // n lines of Pascal's Triangle static void printPascal(int n) { // Iterate through every line // and print entries in it for (int line = 0; line < n; line++) { // Every line has number of // integers equal to line number for (int i = 0; i <= line; i++) System.out.print(binomialCoeff (line, i)+" "); System.out.println(); } } // Link for details of this function static int binomialCoeff(int n, int k) { int res = 1; if (k > n - k) k = n - k; for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // Driver code public static void main(String args[]) { int n = 7; printPascal(n); }}/*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python 3 code for Pascal's Triangle# A simple O(n^3) # program for # Pascal's Triangle# Function to print # first n lines of# Pascal's Triangledef printPascal(n) : # Iterate through every line # and print entries in it for line in range(0, n) : # Every line has number of # integers equal to line # number for i in range(0, line + 1) : print(binomialCoeff(line, i), " ", end = "") print() # for details of this functiondef binomialCoeff(n, k) : res = 1 if (k > n - k) : k = n - k for i in range(0 , k) : res = res * (n - i) res = res // (i + 1) return res# Driver programn = 7printPascal(n)# This code is contributed by Nikita Tiwari. |
C#
// C# code for Pascal's Triangleusing System;class GFG { // Function to print first // n lines of Pascal's Triangle static void printPascal(int n) { // Iterate through every line // and print entries in it for (int line = 0; line < n; line++) { // Every line has number of // integers equal to line number for (int i = 0; i <= line; i++) Console.Write(binomialCoeff (line, i)+" "); Console.WriteLine(); } } // Link for details of this function static int binomialCoeff(int n, int k) { int res = 1; if (k > n - k) k = n - k; for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // Driver code public static void Main() { int n = 7; printPascal(n); }}/*This code is contributed by vt_m.*/ |
Javascript
<script>// Javascript code for Pascal's Triangle // Function to print first // n lines of Pascal's Triangle function printPascal(n) { // Iterate through every line // and print entries in it for (let line = 0; line < n; line++) { // Every line has number of // integers equal to line number for (let i = 0; i <= line; i++) document.write(binomialCoeff (line, i)+" "); document.write("<br />"); } } // Link for details of this function function binomialCoeff(n, k) { let res = 1; if (k > n - k) k = n - k; for (let i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; }// Driver Code let n = 7; printPascal(n);</script> |
PHP
<?php// PHP implementation for// Pascal's Triangle// for details of this functionfunction binomialCoeff($n, $k){ $res = 1; if ($k > $n - $k) $k = $n - $k; for ($i = 0; $i < $k; ++$i) { $res *= ($n - $i); $res /= ($i + 1); }return $res;}// Function to print first// n lines of Pascal's // Trianglefunction printPascal($n){ // Iterate through every line and // print entries in it for ($line = 0; $line < $n; $line++) { // Every line has number of // integers equal to line // number for ($i = 0; $i <= $line; $i++) echo "".binomialCoeff($line, $i)." "; echo "\n"; }}// Driver Code$n=7;printPascal($n);// This code is contributed by Mithun Kumar?> |
Output
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
Time complexity: O(N^3), where N is the number of rows you want to print
Auxiliary Space: O(1)
Pascal’s Triangle
Pascal’s triangle is a triangular array of binomial coefficients. Write a function that takes an integer value N as input and prints the first N lines of Pascal’s triangle.
Example:
The below image shows the Pascal’s Triangle for N=6