A useful application of Pascal’s triangle is the calculation of combinations. The formula to find nCr is n! / r! * (n – r)! which is also the formula for a cell of Pascal’s triangle.
Pascal’s triangle:
Input: n = 5, r = 3
Output: 10
Explanation:
n! / r! * (n - r)! = 5! / 3! * (2!) = 120 / 12 = 10
Input: n = 7, r = 2
Output: 21
Explanation:
n! / r! * (n - r)! = 7! / 5! * (2!) = 42 / 2 = 21
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach 1: The idea is to store the Pascal’s triangle in a matrix then the value of nCr will be the value of the cell at nth row and rth column.
To create the pascal triangle use these two formula:
- nC0 = 1, number of ways to select 0 elements from a set of n elements is 0
- nCr = n-1Cr-1 + n-1Cr, number of ways to select r elements from a set of n elements is summation of ways to select r-1 elements from n-1 elements and ways to select r elements from n-1 elements.
The idea is to use the values of subproblems to calculate the answers for larger values. For example, to calculate nCr, use the values of n-1Cr-1 and n-1Cr. So DP can be used to preprocess all the values in the range.
Algorithm:
- Create a matrix of size 1000 * 1000, assign the value of base cases, i.e. run a loop from 0 to 1000 and assign matrix[i][0] = 1, nC0 = 1
- Run a nested loop from i = 1 to 1000 (outer loop) and the inner loop runs from j = 1 to i + 1.
- For every element (i, j) assign the value of matrix[i][j] = matrix[i-1][j-1] + matrix[i-1][j], using the formula nCr = n-1Cr-1 + n-1Cr
- After filling the matrix return the value of nCr as matrix[n][r]
C++
#include <bits/stdc++.h>
using namespace std;
int l[1001][1001] = { 0 };
void initialize()
{
l[0][0] = 1;
for ( int i = 1; i < 1001; i++) {
l[i][0] = 1;
for ( int j = 1; j < i + 1; j++) {
l[i][j] = (l[i - 1][j - 1] + l[i - 1][j]);
}
}
}
int nCr( int n, int r)
{
return l[n][r];
}
int main()
{
initialize();
int n = 8;
int r = 3;
cout << nCr(n, r);
}
|
Java
class GFG {
static int l[][] = new int [ 1001 ][ 1001 ];
static void initialize()
{
l[ 0 ][ 0 ] = 1 ;
for ( int i = 1 ; i < 1001 ; i++) {
l[i][ 0 ] = 1 ;
for ( int j = 1 ; j < i + 1 ; j++) {
l[i][j] = (l[i - 1 ][j - 1 ] + l[i - 1 ][j]);
}
}
}
static int nCr( int n, int r)
{
return l[n][r];
}
public static void main(String[] args)
{
initialize();
int n = 8 ;
int r = 3 ;
System.out.println(nCr(n, r));
}
}
|
Python3
l = [[ 0 for i in range ( 1001 )] for j in range ( 1001 )]
def initialize():
l[ 0 ][ 0 ] = 1
for i in range ( 1 , 1001 ):
l[i][ 0 ] = 1
for j in range ( 1 , i + 1 ):
l[i][j] = (l[i - 1 ][j - 1 ] + l[i - 1 ][j])
def nCr(n, r):
return l[n][r]
initialize()
n = 8
r = 3
print (nCr(n, r))
|
C#
using System;
class GFG {
static int [, ] l = new int [1001, 1001];
static void initialize()
{
l[0, 0] = 1;
for ( int i = 1; i < 1001; i++) {
l[i, 0] = 1;
for ( int j = 1; j < i + 1; j++) {
l[i, j] = (l[i - 1, j - 1] + l[i - 1, j]);
}
}
}
static int nCr( int n, int r)
{
return l[n, r];
}
public static void Main()
{
initialize();
int n = 8;
int r = 3;
Console.WriteLine(nCr(n, r));
}
}
|
Javascript
<script>
let l =
new Array(1001).fill(0).map(() => new Array(1001).fill(0));
function initialize()
{
l[0][0] = 1;
for (let i = 1; i < 1001; i++) {
l[i][0] = 1;
for (let j = 1; j < i + 1; j++) {
l[i][j] = (l[i - 1][j - 1] + l[i - 1][j]);
}
}
}
function nCr(n, r)
{
return l[n][r];
}
initialize();
let n = 8;
let r = 3;
document.write(nCr(n, r));
</script>
|
- Time Complexity: O(1).
The value of all pairs are precomputed so the time to answer the query is O(1), though some time is taken for precomputation but theoretically the precomputation takes constant time.
- Space Complexity: O(1).
Constant space is required.
Approach 2:
The approach is called “Pascal’s Triangle Method”. It involves constructing Pascal’s triangle and then using the value of the corresponding cell to find nCr. The advantage of this method is that it saves time on calculating factorials by reusing previously computed values.
- Construct Pascal’s triangle with n+1 rows and n+1 columns.
- Traverse to the cell corresponding to the values of n and r.
- The value of that cell is the value of nCr.
- Return the value of nCr.
C++
#include <iostream>
#include <vector>
using namespace std;
int pascals_triangle( int n, int r) {
vector<vector< int >> triangle(n+1, vector< int >(n+1, 0));
for ( int i = 0; i <= n; i++) {
triangle[i][0] = 1;
}
for ( int i = 1; i <= n; i++) {
for ( int j = 1; j <= i; j++) {
triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
}
}
return triangle[n][r];
}
int main() {
int n = 5;
int r = 3;
int nCr = pascals_triangle(n, r);
cout << nCr << endl;
return 0;
}
|
Java
import java.io.*;
class GFG {
public static void main(String[] args)
{
int n = 5 ;
int r = 3 ;
System.out.println(pascals_triangle(n, r));
}
static int pascals_triangle( int n, int r)
{
int triangle[][] = new int [n + 1 ][n + 1 ];
for ( int i = 0 ; i <= n; i++) {
triangle[i][ 0 ] = 1 ;
}
for ( int i = 1 ; i <= n; i++) {
for ( int j = 1 ; j <= i; j++) {
triangle[i][j] = triangle[i - 1 ][j - 1 ]
+ triangle[i - 1 ][j];
}
}
return triangle[n][r];
}
}
|
Python3
def pascals_triangle(n, r):
triangle = [[ 0 ] * (n + 1 ) for _ in range (n + 1 )]
for i in range (n + 1 ):
triangle[i][ 0 ] = 1
for i in range ( 1 , n + 1 ):
for j in range ( 1 , i + 1 ):
triangle[i][j] = triangle[i - 1 ][j - 1 ] + triangle[i - 1 ][j]
return triangle[n][r]
n = 5
r = 3
nCr = pascals_triangle(n, r)
print (nCr)
|
C#
using System;
using System.Collections.Generic;
class Program {
static int pascals_triangle( int n, int r) {
List<List< int >> triangle = new List<List< int >>();
for ( int i = 0; i <= n; i++) {
triangle.Add( new List< int >( new int [n+1]));
triangle[i][0] = 1;
}
for ( int i = 1; i <= n; i++) {
for ( int j = 1; j <= i; j++) {
triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
}
}
return triangle[n][r];
}
static void Main( string [] args) {
int n = 5;
int r = 3;
int nCr = pascals_triangle(n, r);
Console.WriteLine(nCr);
}
}
|
Javascript
function pascalsTriangle(n, r) {
var triangle = new Array(n + 1);
for ( var i = 0; i <= n; i++) {
triangle[i] = new Array(n + 1).fill(0);
}
for ( var i = 0; i <= n; i++) {
triangle[i][0] = 1;
}
for ( var i = 1; i <= n; i++) {
for ( var j = 1; j <= i; j++) {
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
}
return triangle[n][r];
}
var n = 5;
var r = 3;
var nCr = pascalsTriangle(n, r);
console.log(nCr);
|
Time Complexity: O(n^2)
Auxiliary Space: O(n^2)
Approach 3:
It involves calculating nCr. The code efficiently calculates the value of nCr without the need for explicit factorials, resulting in optimized computation.
C++
#include <iostream>
using namespace std;
int pascals_triangle( int n, int r) {
int res = 1;
for ( int i = 0; i < r; i++) {
res = res * (n - i);
res = res / (i + 1);
}
return res;
}
int main() {
int n = 5;
int r = 3;
int nCr = pascals_triangle(n, r);
cout << nCr << endl;
return 0;
}
|
Java
public class GFG {
public static int pascalsTriangle( int n, int r) {
int res = 1 ;
for ( int i = 0 ; i < r; i++) {
res = res * (n - i);
res = res / (i + 1 );
}
return res;
}
public static void main(String[] args) {
int n = 5 ;
int r = 3 ;
int nCr = pascalsTriangle(n, r);
System.out.println(nCr);
}
}
|
Python3
def pascals_triangle(n, r):
res = 1
for i in range (r):
res = res * (n - i)
res = res / / (i + 1 )
return res
def main():
n = 5
r = 3
nCr = pascals_triangle(n, r)
print (nCr)
if __name__ = = "__main__" :
main()
|
C#
using System;
namespace PascalTriangle
{
class GFG
{
static int CalculateBinomialCoefficient( int n, int r)
{
int res = 1;
for ( int i = 0; i < r; i++)
{
res = res * (n - i);
res = res / (i + 1);
}
return res;
}
static void Main( string [] args)
{
int n = 5;
int r = 3;
int nCr = CalculateBinomialCoefficient(n, r);
Console.WriteLine(nCr);
}
}
}
|
Javascript
function calculateBinomialCoefficient(n, r) {
let res = 1;
for (let i = 0; i < r; i++) {
res = res * (n - i);
res = res / (i + 1);
}
return res;
}
function main() {
const n = 5;
const r = 3;
const nCr = calculateBinomialCoefficient(n, r);
console.log(nCr);
}
main();
|
Time Complexity: O(r)
Auxiliary Space: O(1)
Contact Us