Approach 4 : Using Logarithmic Formula

Approach 5 : Using Efficient Computation of Combinations

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:

C++

#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;
}

Java

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));
    }
}

Python

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));
        }
    }
}

Javascript

// 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

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 ^NC_r .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 ⁵C₂ is 10

Input: N = 3, r = 1
Output: 3

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach 4 : Using Logarithmic Formula

The logarithmic formula for nCr is:

Program to calculate value of nCr

Similar Reads

Contact Us