Project Euler Problem 53 Statement
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, $\displaystyle \binom 5 3 = 10$.
In general, $\displaystyle \binom n r = \dfrac{n!}{r!(n-r)!}$, where $r \le n$, $n! = n \times (n-1) \times ... \times 3 \times 2 \times 1$, and $0! = 1$.
It is not until $n = 23$, that a value exceeds one-million: $\displaystyle \binom {23} {10} = 1144066$.
How many, not necessarily distinct, values of $\displaystyle \binom n r$ for $1 \le n \le 100$, are greater than one-million?
Python Source Code
import math
N, K = map(int,input().split())
c = 0
for n in range(2, N+1):
for r in range(2, n//2):
if math.comb(n, r) > K:
c+= (n + 1 - 2*r)
break
print(c) HackerRank version
HackerRank Project Euler 53: How many, not necessarily distinct, values of $^{n}C_r$, for $1\le n\le N$ $(2\le N\le 1000)$, are greater than $K$ $(1\le K\le 10^{18})$?
Solution
Outer Loop (n from 2 to N):The code iterates through each integer n starting from 2 up to and including N. Binomial coefficients for n < 2 are trivial or not meaningful for the solution.
n//2):
For each n, the code iterates through values of r starting from 2 up to half of n (integer division). This is based on the symmetry property of binomial coefficients, where C(n, r) = C(n, n-r). Therefore, checking up to n//2 avoids redundant calculations.
math.comb(n, r) > K):
- The
math.comb(n, r)function computes the binomial coefficient, also known as "n choose r," which represents the number of ways to choose r elements from a set of n elements. - The code checks if this binomial coefficient exceeds the threshold K. If it does, it proceeds to update the counter c.
c += (n + 1 - 2 * r)):
Upon meeting the condition where C(n, r) > K, the code increments the counter c by the value (n + 1 - 2 * r).
Below is a table illustrating how \( (n + 1 - 2 \times r) \) works across different \( n \) and \( r \):
| \( n \) | \( r_{\text{start}} \) | \( (n + 1 - 2 \times r) \) | Explanation |
|---|---|---|---|
| 10 | 3 | 5 | Counts \( r = 3, 4, 5 \) and their symmetric counterparts. |
| 11 | 3 | 5 | Counts \( r = 3, 4, 5 \) and their symmetric counterparts. |
| 100 | 3 | 95 | Counts \( r = 3 \) to \( 50 \) and \( r = 50 \) to \( 98 \). |
| 6 | 2 | 3 | Counts \( r = 2, 3 \) and their symmetric counterparts. |
break):
Once the condition is satisfied for a particular r, the inner loop breaks. For each n, only the first r that satisfies C(n, r) > K is considered, and subsequent r values for the same n are ignored.
After iterating through all relevant n and r values, the final accumulated value of c is printed. This value represents the solution to the problem based on the given inputs N and K.