Approach 5 : Using Efficient Computation of Combinations
The formula for nCr is = n! / r! * (n-r) ! . Let’s imagine r > n-r (or can take reverse ) . Logic here is since in n! and r! we are going to calculate the factorial of r numbers twice and which is no use i.e they will just cancel out each other , so we don’t calculate them instead we would calculate the product of number from (r , n] and product of numbers from 1 to n-r and divide them (here r can be imagined as the maximum of r , n-r ) . Below is the code for above implementation
#include <iostream>
// calculate multiplication of natural numbers from start to end
double Multiplier(int start, int end)
{
if (start == end) {
return start;
}
else {
double res = 1;
while (start <= end) {
res *= start;
start++;
}
return res;
}
}
double nCR(int n, int r)
{
if (n < r) {
return -1;
}
else if (n == r || r == 0) {
return 1;
}
else {
int max_val = std::max(r, n - r);
int min_val = std::min(r, n - r);
double numerator = Multiplier(max_val + 1, n);
double denominator = Multiplier(1, min_val);
return numerator / denominator;
}
}
int main()
{
int n = 20005;
int r = 25;
std::cout << nCR(n, r) << std::endl;
return 0;
// contributed by Naveen (naveenkumar30838)
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static double nCR(int n, int r)
{
if (n < r) {
return -1;
}
if (n == r || r == 0) {
return 1;
}
int max = Math.max(r, n - r);
int min = Math.min(r, n - r);
return (double)(Multiplier(max + 1, n)
/ Multiplier(1, min));
}
// calculate multiplication of natural numbers from start to end
public static double Multiplier(int start, int end)
{
if (start == end) {
return start;
}
double res = 1;
while (start <= end) {
res *= start;
start++;
}
return res;
}
public static void main(String[] args)
{
System.out.println(
nCR(20005, 25)); // ans 2.1443850196899737E82
// Code contributed by Naveen (naveenkumar30838)
}
}
def nCR(n, r):
if n < r:
return -1
if n == r or r == 0:
return 1
max_val = max(r, n - r)
min_val = min(r, n - r)
return Multiplier(max_val + 1, n) / Multiplier(1, min_val)
# calculate multiplication of natural numbers from start to end
def Multiplier(start, end):
if start == end:
return start
res = 1
while start <= end:
res *= start
start += 1
return res
print(nCR(20005, 25))
#contributed by Naveen (naveenkumar30838)
# ans 21443850196899739431852611539526726818562627337667639676891232267646561961531437300
using System;
class GFG {
static double nCR(int n, int r)
{
if (n < r) {
return -1;
}
else if (n == r || r == 0) {
return 1;
}
else {
int max_val = Math.Max(r, n - r);
int min_val = Math.Min(r, n - r);
double numerator = Multiplier(max_val + 1, n);
double denominator = Multiplier(1, min_val);
return numerator / denominator;
}
}
// calculate multiplication of natural numbers from start to end
static double Multiplier(int start, int end)
{
if (start == end) {
return start;
}
else {
double res = 1;
while (start <= end) {
res *= start;
start++;
}
return res;
}
}
static void Main(string[] args)
{
int n = 20005;
int r = 25;
Console.WriteLine($ "{nCR(n, r)}");
// Contributed by Naveen(naveenkumar30838)
// ans 2.1443850196899737E82
}
}
// Calculate multiplication of natural numbers from start to end
function multiplier(start, end) {
if (start === end) {
return start;
} else {
let res = 1;
while (start <= end) {
res *= start;
start++;
}
return res;
}
}
// Function to calculate n choose r (nCr)
function nCR(n, r) {
if (n < r) {
return -1;
} else if (n === r || r === 0) {
return 1;
} else {
const maxVal = Math.max(r, n - r);
const minVal = Math.min(r, n - r);
const numerator = multiplier(maxVal + 1, n);
const denominator = multiplier(1, minVal);
return numerator / denominator;
}
}
// Example usage
const n = 20005;
const r = 25;
console.log(nCR(n, r));
Output : 2.1443850196899737E82
Time complexity : O(n)
Space complexity : O(1)
Complexity Analysis : In every case (including worst case ) we have to calculate the multiplier from (n-r) and from (1 to r ) which give run in linear time giving a total time complexity of O(n-r +r ) = O(n) . Since no extra space is used so space complexity if O(1) . Since we have eliminated the repeated steps so it is a more optimized solution and hence it can be used for handling large values .
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