Write a Java program to find the value of combination formula i.e nCr.
The above formula is used in mathematics to calculate the combination value, and we will use the same in our java program.
For this, we will write a separate function that will compute and return the factorial of the passed number as an argument.
Using the factorial function we will find the values of n!, (n-r)! and r! and then the result by applying the arithmetic operation as stated by the formula in the above image.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("Enter n"); int n = in.nextInt(); System.out.println("Enter r"); int r = in.nextInt(); int combination = factorial(n)/(factorial(n-r)*factorial(r)); System.out.println("nCr: "+combination); } //Function to return factorial private static int factorial(int num){ if(num==0 || num==1) return 1; int fact = 1; for(int i=2; i<=num; i++){ fact = fact*i; } return fact; } } |
Output
The above method is not so efficient for large numbers because calculating factorial for enormous value of n becomes overhead, especially in competitive programming.
There is one more way to calculate a combination in Java using the second formula as depicted in the 1st Image.
Efficient way to Calculate Combination in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("Enter n"); int n = in.nextInt(); System.out.println("Enter r"); int r = in.nextInt(); System.out.println("nCr: "+nCr(n,r)); } private static int nCr(int n, int r){ if(n<r || n==0) return 1; int num = 1, den = 1; for(int i=r; i>=1; i--){ num = num * n--; den = den * i; } return num/den; } } |
Output
If you know a better way to find the combination, then please comment below.