Which is better way to calculate nCr

user_1347366 0
Viewed 62634

Approach 1:
C(n,r) = n!/(n-r)!r!

Approach 2:
In the book Combinatorial Algorithms by wilf, i have found this:
C(n,r) can be written as C(n-1,r) + C(n-1,r-1).

e.g. 

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

As you can see, the final solution doesn't need any multiplication. In every form C(n,r), either n==r or r==1.

Here is the sample code i have implemented:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

See output here.

In the approach 2, there are overlapping sub-problems where we are calling recursion to solve the same sub-problems again. We can avoid it by using Dynamic Programming.

I want to know which is the better way to calculate C(n,r)?.

binomial-coefficients mathematical-optimization c algorithm performance
5 Answers

Using dynamic programming you can easily find the nCr here is the solution

package com.practice.competitive.maths;

import java.util.Scanner;

public class NCR1 {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int testCase = scanner.nextInt();
            while (testCase-- > 0) {
                int n = scanner.nextInt();
                int r = scanner.nextInt();
                int[][] combination = combination();
                System.out.println(combination[n][r]%1000000007);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static int[][] combination() {
        int combination[][] = new int[1001][1001];
        for (int i = 0; i < 1001; i++)
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i)
                    combination[i][j] = 1;
                else
                    combination[i][j] = combination[i - 1][j - 1] % 1000000007 + combination[i - 1][j] % 1000000007;
            }
        return combination;
    }
}
user_60119410
Related