Program to Calculate the value of nCr
Approach 1 : Using Factorial
The total number of ways for selecting r elements out of n options are nCr = (n!) / (r! * (n-r)!)
where n! = 1 * 2 * . . . * n.
Below is the Implementation of the above approach:
// CPP program To calculate The Value Of nCr
#include <bits/stdc++.h>
using namespace std;
long nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Returns factorial of n
long fact(int n)
{
if(n==0)
return 1;
long res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Driver code
int main()
{
int n = 5, r = 3;
cout << nCr(n, r);
return 0;
}
#include <stdio.h>
long factorial(int n) {
if(n == 0 || n==1)
return 1;
long factorial = 1;
for (int i = 2; i <= n; i++)
factorial = factorial * i;
return factorial;
}
long nCr(int n, int r) {
return factorial(n) / (factorial(r) * factorial(n - r));
}
int main() {
int n = 5, r = 3;
printf("%d", nCr(n, r));
return 0;
}
// This code was contributed by Omkar Prabhune
// Java program To calculate
// The Value Of nCr
import java.io.*;
public class GFG {
static long nCr(int n, int r)
{
return fact(n) / (fact(r) *
fact(n - r));
}
// Returns factorial of n
static long fact(int n)
{
if(n==0 || n==1)
return 1;
long res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Driver code
public static void main(String[] args)
{
int n = 5, r = 3;
System.out.println(nCr(n, r));
}
}
// This code is Contributed by
// Smitha Dinesh Semwal.
# Python 3 program To calculate
# The Value Of nCr
def nCr(n, r):
return (fact(n) / (fact(r)
* fact(n - r)))
# Returns factorial of n
def fact(n):
if n == 0 or n==1:
return 1
res = 1
for i in range(2, n+1):
res = res * i
return res
# Driver code
n = 5
r = 3
print(int(nCr(n, r)))
# This code is contributed
# by Smitha and improved by naveenkumar30838
// C# program To calculate
// The Value Of nCr
using System;
class GFG {
static long nCr(int n, int r)
{
return fact(n) / (fact(r) *
fact(n - r));
}
// Returns factorial of n
static long fact(int n)
{
if(n==0 || n==1)
return 1;
long res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Driver code
public static void Main()
{
int n = 5, r = 3;
Console.Write(nCr(n, r));
}
}
// This code is Contributed by nitin mittal and improved by naveenkumar30838
<script>
// Javascript program To calculate The Value Of nCr
function nCr(n, r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Returns factorial of n
function fact(n)
{
if(n==0 || n==1)
return 1;
var res = 1;
for (var i = 2; i <= n; i++)
res = res * i;
return res;
}
// Driver code
var n = 5, r = 3;
document.write(nCr(n, r));
</script>
<?php
// PHP program To calculate
// the Value Of nCr
function nCr( $n, $r)
{
return fact($n) / (fact($r) *
fact($n - $r));
}
// Returns factorial of n
function fact( $n)
{
if($n == 0 || $n==1)
return 1;
$res = 1;
for ( $i = 2; $i <= $n; $i++)
$res = $res * $i;
return $res;
}
// Driver code
$n = 5;
$r = 3;
echo nCr($n, $r);
// This code is contributed by vt_m.
?>
Output
10
Time Complexity: O(N)
Auxiliary Space: O(1)
Complexity Analysis:
The time complexity of the above approach is O(N).
This is because the function fact() has a time complexity of O(N), and it is called twice for each call to nCr().
The space complexity of the above approach is O(1).
Because the function does not make any recursive calls and only uses a constant amount of memory.
Approach 2 : Using Recursion
The idea is to use a recursive function to calculate the value of nCr. The base cases are:
- if r is greater than n, return 0 (there are no combinations possible)
- if r is 0 or r is n, return 1 (there is only 1 combination possible in these cases)
For other values of n and r, the function calculates the value of nCr by adding the number of combinations possible by including the current element and the number of combinations possible by not including the current element.
Below is the Implementation of the above approach:
#include <iostream>
using namespace std;
int nCr(int n, int r)
{
if (r > n)
return 0;
if (r == 0 || r == n)
return 1;
return nCr(n - 1, r - 1) + nCr(n - 1, r);
}
int main()
{
cout << nCr(5, 3); // Output: 10
return 0;
}
// This code is contributed by Susobhan Akhuli
import java.util.*;
class GFG {
public static int nCr(int n, int r)
{
if (r > n)
return 0;
if (r == 0 || r == n)
return 1;
return nCr(n - 1, r - 1) + nCr(n - 1, r);
}
public static void main(String[] args)
{
System.out.println(nCr(5, 3)); // Output: 10
}
}
// This code is contributed by Prasad Kandekar(prasad264)
def nCr(n, r):
if r > n:
return 0
if r == 0 or r == n:
return 1
return nCr(n-1, r-1) + nCr(n-1, r)
print(nCr(5, 3)) # Output: 10
# This code is contributed by Susobhan Akhuli
using System;
public class GFG {
static public int nCr(int n, int r)
{
if (r > n)
return 0;
if (r == 0 || r == n)
return 1;
return nCr(n - 1, r - 1) + nCr(n - 1, r);
}
static public void Main(string[] args)
{
Console.WriteLine(nCr(5, 3)); // Output: 10
}
}
// This code is contributed by Prasad Kandekar(prasad264)
function nCr(n, r) {
if (r > n)
return 0;
if (r === 0 || r === n)
return 1;
return nCr(n-1, r-1) + nCr(n-1, r);
}
console.log(nCr(5, 3)); // Output: 10
// This code is contributed by Prasad Kandekar(prasad264)
Output
10
Time Complexity: O(2N)
Auxiliary Space: O(N2)
Approach 3 : Using Binomial Coefficient formula
- A binomial coefficient C(n, k) can be defined as the coefficient of Xk in the expansion of (1 + X)n.
- A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.
Iterative way of calculating NCR. using binomial coefficient formula.
#include <iostream>
using namespace std;
int main() {
int n = 5;
int r = 2;
double sum = 1;
// Calculate the value of n choose r using the binomial coefficient formula
for(int i = 1; i <= r; i++){
sum = sum * (n - r + i) / i;
}
cout<<(int)sum<<endl;
return 0;
}
import java.util.*;
public class BinomialCoefficient {
public static void main(String[] args)
{
int n = 5;
int r = 2;
double sum = 1;
// Calculate the value of n choose r using the
// binomial coefficient formula
for (int i = 1; i <= r; i++) {
sum = sum * (n - r + i) / i;
}
// Print the result after converting it to an
// integer
System.out.println((int)sum);
}
}
n = 5
r = 2
sum = 1
# Calculate the value of n choose r using the binomial coefficient formula
for i in range(1, r+1):
sum = sum * (n - r + i) / i
print(int(sum))
# This code is contributed by divyansh2212
using System;
// C# code implementation
class HelloWorld {
static void Main() {
int n = 5;
int r = 2;
double sum = 1;
// Calculate the value of n choose r using the binomial coefficient formula
for(int i = 1; i <= r; i++){
sum = sum * (n - r + i) / i;
}
Console.WriteLine((int)sum);
}
}
// The code is contributed by Arushi jindal.
let n = 5;
let r = 2;
let sum = 1;
// Calculate the value of n choose r using the binomial coefficient formula
for(let i = 1; i <= r; i++){
sum = sum * (n - r + i) / i;
}
console.log(Math.floor(sum));
// This code is contributed by prasad264
Output
10
Time complexity : O(r)
Space complexity : O(1)
Program to calculate value of nCr
Given two numbers N and r, The task is to find the value of NCr . Combinations represent the number of ways to choose r elements from a set of n distinct elements, without regard to the order in which they are selected. The formula for calculating combinations is :
C(n,r) = n! / r! * (n-r) !
Where :
- (n!) represents the factorial of n .
- (r!) represents the factorial of r .
Examples :
Input: N = 5, r = 2
Output: 10
Explanation: The value of 5C2 is 10Input: N = 3, r = 1
Output: 3
Contact Us