Approach 4 : Using Logarithmic Formula
Logarithmic formula for nCr is an alternative to the factorial formula that avoids computing factorials directly and it’s more efficient for large values of n and r. It uses the identity log(n!) = log(1) + log(2) + … + log(n) to express the numerator and denominator of the nCr in terms of sums of logarithms which allows to calculate the nCr using the Logarithmic operations. This approach is faster and very efficient.
The logarithmic formula for nCr is:
nCr = exp( log(n!) – log(r!) – log((n-r)!) )
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
// Calculates the binomial coefficient nCr using the logarithmic formula
int nCr(int n, int r) {
// If r is greater than n, return 0
if (r > n) return 0;
// If r is 0 or equal to n, return 1
if (r == 0 || n == r) return 1;
// Initialize the logarithmic sum to 0
double res = 0;
// Calculate the logarithmic sum of the numerator and denominator using loop
for (int i = 0; i < r; i++) {
// Add the logarithm of (n-i) and subtract the logarithm of (i+1)
res += log(n-i) - log(i+1);
}
// Convert logarithmic sum back to a normal number
return (int)round(exp(res));
}
int main() {
// Calculate nCr for n = 5 and r = 2
int n = 5;
int r = 2;
cout << nCr(n, r) << endl;
return 0;
}
import java.util.*;
public class GFG {
// Calculates the binomial coefficient nCr using the logarithmic formula
static int nCr(int n, int r) {
// If r is greater than n, return 0
if (r > n)
return 0;
// If r is 0 or equal to n, return 1
if (r == 0 || n == r)
return 1;
// Initialize the logarithmic sum to 0
double res = 0;
// Calculate the logarithmic sum of the numerator and denominator using loop
for (int i = 0; i < r; i++) {
// Add the logarithm of (n-i) and subtract the logarithm of (i+1)
res += Math.log(n - i) - Math.log(i + 1);
}
// Convert logarithmic sum back to a normal number
return (int) Math.round(Math.exp(res));
}
public static void main(String[] args) {
// Calculate nCr for n = 5 and r = 2
int n = 5;
int r = 2;
System.out.println(nCr(n, r));
}
}
import math
# Calculates the binomial coefficient nCr using the logarithmic formula
def nCr(n, r):
# If r is greater than n, return 0
if r > n:
return 0
# If r is 0 or equal to n, return 1
if r == 0 or n == r:
return 1
# Initialize the logarithmic sum to 0
res = 0
# Calculate the logarithmic sum of the numerator and denominator using loop
for i in range(r):
# Add the logarithm of (n-i) and subtract the logarithm of (i+1)
res += math.log(n-i) - math.log(i+1)
# Convert logarithmic sum back to a normal number
return round(math.exp(res))
# Test case
n = 5
r = 2
print(nCr(n, r))
using System;
namespace BinomialCoefficient
{
class Program
{
// Calculates the binomial coefficient nCr using the logarithmic formula
static int nCr(int n, int r)
{
// If r is greater than n, return 0
if (r > n) return 0;
// If r is 0 or equal to n, return 1
if (r == 0 || n == r) return 1;
// Initialize the logarithmic sum to 0
double res = 0;
// Calculate the logarithmic sum of the numerator and denominator using loop
for (int i = 0; i < r; i++)
{
// Add the logarithm of (n-i) and subtract the logarithm of (i+1)
res += Math.Log(n - i) - Math.Log(i + 1);
}
// Convert logarithmic sum back to a normal number
return (int)Math.Round(Math.Exp(res));
}
static void Main(string[] args)
{
// Calculate nCr for n = 5 and r = 2
int n = 5;
int r = 2;
Console.WriteLine(nCr(n, r));
}
}
}
// Calculates the binomial coefficient nCr using the logarithmic formula
function nCr(n, r) {
// If r is greater than n, return 0
if (r > n) return 0;
// If r is 0 or equal to n, return 1
if (r === 0 || n === r) return 1;
// Initialize the logarithmic sum to 0
let res = 0;
// Calculate the logarithmic sum of the numerator and denominator using loop
for (let i = 0; i < r; i++) {
// Add the logarithm of (n-i) and subtract the logarithm of (i+1)
res += Math.log(n - i) - Math.log(i + 1);
}
// Convert logarithmic sum back to a normal number
return Math.round(Math.exp(res));
}
// Test case
const n = 5;
const r = 2;
console.log(nCr(n, r));
Output
10
Time Complexity: O(r)
Auxiliary Space: 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