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