Solution to Project Euler Problem 53: Combinatoric selections - There are exactly ten ways of selecting three from five, 12345:
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
In combinatorics, we use the notation, (5 C 3) = 10.
In general. (n C r) = n!/r!(n-r)!, where r ≤ n, n! = n x (n - 1) x ... 3 x 2 x 1, and 0! = 1.
Updated: Jan. 16, 2021 — Training Time: 2 minutes
Overseen by: Archangel Macsika
All Training Resources
Scroll for more menu list
Topic: Project Euler Problem 53: Combinatoric selections.
Difficulty: Easy.
Objective: There are exactly ten ways of selecting three from five, 12345:
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
In combinatorics, we use the notation, (5 C 3) = 10.
In general, (n C r) = n!/r!(n-r)!, where r ≤ n, n! = n x (n - 1) x ... 3 x 2 x 1, and 0! = 1.
It is not until n = 23, that a value exceeds one-million: (23 C 10) = 1144066.
How many, not necessarily distinct, values of (n C r) for 1 ≤ n ≤ 100, are greater than one-million?
Input: None.
Expected Output: 4075.
Sikademy Solution in Java Programming Language
package sikademy;
/**
*
* @author Archangel Macsika
* Copyright (c) Sikademy. All rights reserved
*/
import java.math.BigInteger;
public class SikademyEulerSolution {
public String run() {
BigInteger MILLION = BigInteger.TEN.pow(6);
int count = 0;
for (int n = 1; n <= 100; n++) {
for (int r = 0; r <= n; r++) {
if (binomial(n, r).compareTo(MILLION) > 0)
count++;
}
}
return Integer.toString(count);
}
public static BigInteger binomial(int n, int k) {
if (k < 0 || k > n)
throw new IllegalArgumentException();
BigInteger product = BigInteger.ONE;
for (int i = 0; i < k; i++)
product = product.multiply(BigInteger.valueOf(n - i));
return product.divide(factorial(k));
}
public static void main(String[] args) {
SikademyEulerSolution solution = new SikademyEulerSolution();
System.out.println(solution.run());
}
}
Sikademy Solution in Python Programming Language
#
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
#
import math
def compute():
ans = sum(1
for n in range(1, 101)
for k in range(0, n + 1)
if binomial(n, k) > 1000000)
return str(ans)
def binomial(n, k):
assert 0 <= k <= n
return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
if __name__ == "__main__":
print(compute())