Skip to main content

Calculate value of ncr efficiently

The formula to calculate nCr, also known as the combination of n things taken r at a time, is:

nCr = n! / (r! * (n-r)!)

Where "n" is the total number of things, and "r" is the number of things taken at a time.

Let's break down this formula into simpler terms.

Firstly, the exclamation mark, or factorial, means to multiply all the whole numbers from the given number down to 1. For example, 5! = 5 x 4 x 3 x 2 x 1 = 120.

In the nCr formula, we have to calculate the factorials of both "n" and "r". Then we multiply the factorial of "r" with the factorial of "n-r". Finally, we divide the factorial of "n" with the result of the previous multiplication.

For example, if we want to find the value of 5C2, we will plug in "n=5" and "r=2" into the formula:

5C2 = 5! / (2! * (5-2)!) = 5 x 4 x 3 x 2 x 1 / [(2 x 1) x (3 x 2 x 1)] = 10

Therefore, the value of 5C2 is 10, which means there are 10 ways to choose 2 items out of 5.

In summary, nCr is a formula to calculate the number of ways we can choose "r" items from a total of "n" items. It involves calculating factorials and is a fundamental concept in combinatorics, probability, and statistics.

Code Solution

/*
    Java program
    Calculate value of ncr efficiently
*/
public class Combinations
{
	// Returns the gcd value of two numbers
	public long gcd(long a, long b)
	{
		if (b == 0)
		{
			return a;
		}
		return gcd(b, a % b);
	}
	public void findNcR(int objects, int subset)
	{
		int n = objects;
		int r = subset;
		// Formula of nCr 
		// nCr = n!/[r!(n-r)!]
		// Here
		// C : Indicates number of combination
		// n : Number of objects in set
		// r : Subset size
		long p = 1;
		long k = 1;
		if (n - r < r)
		{
			// Change r when (n - r) is smaller to r
			r = n - r;
		}
		if (r != 0)
		{
			while (r >= 1)
			{
				p = p * n;
				k = k * r;
				// Reduce the value of  n and r by 1
				n--;
				r--;
				// Get gcd of p and k
				long d = gcd(p, k);
				// Divide p and k by d
				// d is common divisor
				p = p / d;
				k = k / d;
			}
		}
		else
		{
			p = 1;
		}
		// Display given value
		System.out.println(" Given n : " + objects + " r : " + subset);
		// Display calculated result
		System.out.println(" Result  : " + p);
	}
	public static void main(String[] args)
	{
		Combinations task = new Combinations();
		// Test Case
		task.findNcR(7, 2);
		task.findNcR(12, 3);
	}
}

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
// Include header file
#include <iostream>
using namespace std;

/*
    C++ program
    Calculate value of ncr efficiently
*/

class Combinations
{
	public:
		// Returns the gcd value of two numbers
		long gcd(long a, long b)
		{
			if (b == 0)
			{
				return a;
			}
			return this->gcd(b, a % b);
		}
	void findNcR(int objects, int subset)
	{
		int n = objects;
		int r = subset;
		// Formula of nCr 
		// nCr = n!/[r!(n-r)!]
		// Here
		// C : Indicates number of combination
		// n : Number of objects in set
		// r : Subset size
		long p = 1;
		long k = 1;
		if (n - r < r)
		{
			// Change r when (n - r) is smaller to r
			r = n - r;
		}
		if (r != 0)
		{
			while (r >= 1)
			{
				p = p *n;
				k = k *r;
				// Reduce the value of  n and r by 1
				n--;
				r--;
				// Get gcd of p and k
				long d = this->gcd(p, k);
				// Divide p and k by d
				// d is common divisor
				p = p / d;
				k = k / d;
			}
		}
		else
		{
			p = 1;
		}
		// Display given value
		cout << " Given n : " << objects << " r : " << subset << endl;
		// Display calculated result
		cout << " Result  : " << p << endl;
	}
};
int main()
{
	Combinations *task = new Combinations();
	// Test Case
	task->findNcR(7, 2);
	task->findNcR(12, 3);
	return 0;
}

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
// Include namespace system
using System;
/*
    Csharp program
    Calculate value of ncr efficiently
*/
public class Combinations
{
	// Returns the gcd value of two numbers
	public long gcd(long a, long b)
	{
		if (b == 0)
		{
			return a;
		}
		return this.gcd(b, a % b);
	}
	public void findNcR(int objects, int subset)
	{
		int n = objects;
		int r = subset;
		// Formula of nCr 
		// nCr = n!/[r!(n-r)!]
		// Here
		// C : Indicates number of combination
		// n : Number of objects in set
		// r : Subset size
		long p = 1;
		long k = 1;
		if (n - r < r)
		{
			// Change r when (n - r) is smaller to r
			r = n - r;
		}
		if (r != 0)
		{
			while (r >= 1)
			{
				p = p * n;
				k = k * r;
				// Reduce the value of  n and r by 1
				n--;
				r--;
				// Get gcd of p and k
				long d = this.gcd(p, k);
				// Divide p and k by d
				// d is common divisor
				p = p / d;
				k = k / d;
			}
		}
		else
		{
			p = 1;
		}
		// Display given value
		Console.WriteLine(" Given n : " + objects + " r : " + subset);
		// Display calculated result
		Console.WriteLine(" Result  : " + p);
	}
	public static void Main(String[] args)
	{
		Combinations task = new Combinations();
		// Test Case
		task.findNcR(7, 2);
		task.findNcR(12, 3);
	}
}

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
<?php
/*
    Php program
    Calculate value of ncr efficiently
*/
class Combinations
{
	// Returns the gcd value of two numbers
	public	function gcd($a, $b)
	{
		if ($b == 0)
		{
			return $a;
		}
		return $this->gcd($b, $a % $b);
	}
	public	function findNcR($objects, $subset)
	{
		$n = $objects;
		$r = $subset;
		// Formula of nCr 
		// nCr = n!/[r!(n-r)!]
		// Here
		// C : Indicates number of combination
		// n : Number of objects in set
		// r : Subset size
		$p = 1;
		$k = 1;
		if ($n - $r < $r)
		{
			// Change r when (n - r) is smaller to r
			$r = $n - $r;
		}
		if ($r != 0)
		{
			while ($r >= 1)
			{
				$p = $p * $n;
				$k = $k * $r;
				// Reduce the value of  n and r by 1
				$n--;
				$r--;
				// Get gcd of p and k
				$d = $this->gcd($p, $k);
				// Divide p and k by d
				// d is common divisor
				$p = $p / $d;
				$k = $k / $d;
			}
		}
		else
		{
			$p = 1;
		}
		// Display given value
		echo(" Given n : ".$objects.
			" r : ".$subset.
			"\n");
		// Display calculated result
		echo(" Result  : ".$p.
			"\n");
	}
}

function main()
{
	$task = new Combinations();
	// Test Case
	$task->findNcR(7, 2);
	$task->findNcR(12, 3);
}
main();

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
/*
    Node JS program
    Calculate value of ncr efficiently
*/
class Combinations
{
	// Returns the gcd value of two numbers
	gcd(a, b)
	{
		if (b == 0)
		{
			return a;
		}
		return this.gcd(b, a % b);
	}
	findNcR(objects, subset)
	{
		var n = objects;
		var r = subset;
		// Formula of nCr 
		// nCr = n!/[r!(n-r)!]
		// Here
		// C : Indicates number of combination
		// n : Number of objects in set
		// r : Subset size
		var p = 1;
		var k = 1;
		if (n - r < r)
		{
			// Change r when (n - r) is smaller to r
			r = n - r;
		}
		if (r != 0)
		{
			while (r >= 1)
			{
				p = p * n;
				k = k * r;
				// Reduce the value of  n and r by 1
				n--;
				r--;
				// Get gcd of p and k
				var d = this.gcd(p, k);
				// Divide p and k by d
				// d is common divisor
				p = p / d;
				k = k / d;
			}
		}
		else
		{
			p = 1;
		}
		// Display given value
		console.log(" Given n : " + objects + " r : " + subset);
		// Display calculated result
		console.log(" Result  : " + p);
	}
}

function main()
{
	var task = new Combinations();
	// Test Case
	task.findNcR(7, 2);
	task.findNcR(12, 3);
}
main();

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
#    Python 3 program
#    Calculate value of ncr efficiently
class Combinations :
	#  Returns the gcd value of two numbers
	def gcd(self, a, b) :
		if (b == 0) :
			return a
		
		return self.gcd(b, a % b)
	
	def findNcR(self, objects, subset) :
		n = objects
		r = subset
		#  Formula of nCr 
		#  nCr = n!/[r!(n-r)!]
		#  Here
		#  C : Indicates number of combination
		#  n : Number of objects in set
		#  r : Subset size
		p = 1
		k = 1
		if (n - r < r) :
			#  Change r when (n - r) is smaller to r
			r = n - r
		
		if (r != 0) :
			while (r >= 1) :
				p = p * n
				k = k * r
				#  Reduce the value of  n and r by 1
				n -= 1
				r -= 1
				#  Get gcd of p and k
				d = self.gcd(p, k)
				#  Divide p and k by d
				#  d is common divisor
				p = int(p / d)
				k = int(k / d)
			
		else :
			p = 1
		
		#  Display given value
		print(" Given n : ", objects ," r : ", subset)
		#  Display calculated result
		print(" Result  : ", p)
	

def main() :
	task = Combinations()
	#  Test Case
	task.findNcR(7, 2)
	task.findNcR(12, 3)

if __name__ == "__main__": main()

input

 Given n :  7  r :  2
 Result  :  21
 Given n :  12  r :  3
 Result  :  220
#    Ruby program
#    Calculate value of ncr efficiently
class Combinations 
	#  Returns the gcd value of two numbers
	def gcd(a, b) 
		if (b == 0) 
			return a
		end

		return self.gcd(b, a % b)
	end

	def findNcR(objects, subset) 
		n = objects
		r = subset
		#  Formula of nCr 
		#  nCr = n!/[r!(n-r)!]
		#  Here
		#  C : Indicates number of combination
		#  n : Number of objects in set
		#  r : Subset size
		p = 1
		k = 1
		if (n - r < r) 
			#  Change r when (n - r) is smaller to r
			r = n - r
		end

		if (r != 0) 
			while (r >= 1) 
				p = p * n
				k = k * r
				#  Reduce the value of  n and r by 1
				n -= 1
				r -= 1
				#  Get gcd of p and k
				d = self.gcd(p, k)
				#  Divide p and k by d
				#  d is common divisor
				p = p / d
				k = k / d
			end

		else
 
			p = 1
		end

		#  Display given value
		print(" Given n : ", objects ," r : ", subset, "\n")
		#  Display calculated result
		print(" Result  : ", p, "\n")
	end

end

def main() 
	task = Combinations.new()
	#  Test Case
	task.findNcR(7, 2)
	task.findNcR(12, 3)
end

main()

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220

/*
    Scala program
    Calculate value of ncr efficiently
*/
class Combinations()
{
	// Returns the gcd value of two numbers
	def gcd(a: Long, b: Long): Long = {
		if (b == 0)
		{
			return a;
		}
		return gcd(b, a % b);
	}
	def findNcR(objects: Int, subset: Int): Unit = {
		var n: Int = objects;
		var r: Int = subset;
		// Formula of nCr 
		// nCr = n!/[r!(n-r)!]
		// Here
		// C : Indicates number of combination
		// n : Number of objects in set
		// r : Subset size
		var p: Long = 1;
		var k: Long = 1;
		if (n - r < r)
		{
			// Change r when (n - r) is smaller to r
			r = n - r;
		}
		if (r != 0)
		{
			while (r >= 1)
			{
				p = p * n;
				k = k * r;
				// Reduce the value of  n and r by 1
				n -= 1;
				r -= 1;
				// Get gcd of p and k
				var d: Long = gcd(p, k);
				// Divide p and k by d
				// d is common divisor
				p = p / d;
				k = k / d;
			}
		}
		else
		{
			p = 1;
		}
		// Display given value
		println(" Given n : " + objects + " r : " + subset);
		// Display calculated result
		println(" Result  : " + p);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Combinations = new Combinations();
		// Test Case
		task.findNcR(7, 2);
		task.findNcR(12, 3);
	}
}

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
/*
    Swift 4 program
    Calculate value of ncr efficiently
*/
class Combinations
{
	// Returns the gcd value of two numbers
	func gcd(_ a: Int, _ b: Int) -> Int
	{
		if (b == 0)
		{
			return a;
		}
		return self.gcd(b, a % b);
	}
	func findNcR(_ objects: Int, _ subset: Int)
	{
		var n: Int = objects;
		var r: Int = subset;
		// Formula of nCr 
		// nCr = n!/[r!(n-r)!]
		// Here
		// C : Indicates number of combination
		// n : Number of objects in set
		// r : Subset size
		var p: Int = 1;
		var k: Int = 1;
		if (n - r < r)
		{
			// Change r when (n - r) is smaller to r
			r = n - r;
		}
		if (r  != 0)
		{
			while (r >= 1)
			{
				p = p * n;
				k = k * r;
				// Reduce the value of  n and r by 1
				n -= 1;
				r -= 1;
				// Get gcd of p and k
				let d: Int = self.gcd(p, k);
				// Divide p and k by d
				// d is common divisor
				p = p / d;
				k = k / d;
			}
		}
		else
		{
			p = 1;
		}
		// Display given value
		print(" Given n : ", objects ," r : ", subset);
		// Display calculated result
		print(" Result  : ", p);
	}
}
func main()
{
	let task: Combinations = Combinations();
	// Test Case
	task.findNcR(7, 2);
	task.findNcR(12, 3);
}
main();

input

 Given n :  7  r :  2
 Result  :  21
 Given n :  12  r :  3
 Result  :  220
/*
    Kotlin program
    Calculate value of ncr efficiently
*/
class Combinations
{
	// Returns the gcd value of two numbers
	fun gcd(a: Long, b: Long): Long
	{
		if (b == 0L)
		{
			return a;
		}
		return this.gcd(b, a % b);
	}
	fun findNcR(objects: Int, subset: Int): Unit
	{
		var n: Int = objects;
		var r: Int = subset;
		// Formula of nCr 
		// nCr = n!/[r!(n-r)!]
		// Here
		// C : Indicates number of combination
		// n : Number of objects in set
		// r : Subset size
		var p: Long = 1;
		var k: Long = 1;
		if (n - r < r)
		{
			// Change r when (n - r) is smaller to r
			r = n - r;
		}
		if (r != 0)
		{
			while (r >= 1)
			{
				p = p * n;
				k = k * r;
				// Reduce the value of  n and r by 1
				n -= 1;
				r -= 1;
				// Get gcd of p and k
				val d: Long = this.gcd(p, k);
				// Divide p and k by d
				// d is common divisor
				p = p / d;
				k = k / d;
			}
		}
		else
		{
			p = 1;
		}
		// Display given value
		println(" Given n : " + objects + " r : " + subset);
		// Display calculated result
		println(" Result  : " + p);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Combinations = Combinations();
	// Test Case
	task.findNcR(7, 2);
	task.findNcR(12, 3);
}

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
package main
import "fmt"
/*
    Go program
    Calculate value of ncr efficiently
*/

// Returns the gcd value of two numbers
func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a % b)
}
func findNcR(objects, subset int) {
	var n int = objects
	var r int = subset
	// Formula of nCr 
	// nCr = n!/[r!(n-r)!]
	// Here
	// C : Indicates number of combination
	// n : Number of objects in set
	// r : Subset size
	var p int = 1
	var k int = 1
	if n - r < r {
		// Change r when (n - r) is smaller to r
		r = n - r
	}
	if r != 0 {
		for (r >= 1) {
			p = p * n
			k = k * r
			// Reduce the value of  n and r by 1
			n--
			r--
			// Get gcd of p and k
			var d int =  gcd(p, k)
			// Divide p and k by d
			// d is common divisor
			p = p / d
			k = k / d
		}
	} else {
		p = 1
	}
	// Display given value
	fmt.Println(" Given n : ", objects, " r : ", subset)
	// Display calculated result
	fmt.Println(" Result  : ", p)
}
func main() {
	// Test Case
	findNcR(7, 2)
	findNcR(12, 3)
}

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
/*
    Rust program
    Calculate value of ncr efficiently
*/
fn main(){
	// Test Case
	find_n_c_r(7, 2);
	find_n_c_r(12, 3);
}
// Returns the gcd value of two numbers
fn  gcd( a: i32, b: i32) -> i32
{
	if b == 0
	{
		return a;
	}
	return gcd(b, a % b);
}
fn find_n_c_r( objects: i32, subset: i32)
{
	let mut n: i32 = objects;
	let mut r: i32 = subset;
	// Formula of nCr 
	// nCr = n!/[r!(n-r)!]
	// Here
	// C : Indicates number of combination
	// n : Number of objects in set
	// r : Subset size
	let mut p = 1;
	let mut k = 1;
	if (n - r) < r
	{
		// Change r when (n - r) is smaller to r
		r = n - r;
	}
	if r != 0
	{
		while r >= 1
		{
			p = p * n;
			k = k * r;
			// Reduce the value of  n and r by 1
			n=n-1;
			r=r-1;
			// Get gcd of p and k
			let d =  gcd(p, k);
			// Divide p and k by d
			// d is common divisor
			p = p / d;
			k = k / d;
		}
	}
	else
	{
		p = 1;
	}
	// Display given value
	println!(" Given n : {0} r : {1} ", objects , subset);
	// Display calculated result
	println!(" Result  : {0}" , p);
}

input

 Given n : 7 r : 2
 Result  : 21
 Given n : 12 r : 3
 Result  : 220
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment