Project Euler Problem 53 Solution

Project Euler Problem 53 Solution

Combinatoric Selections

by {BetaProjects} | Project Euler & HackerRank

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, 5C3 = 10.
In general, nCr = n! / r!(n−r)!, where rn, n! = n×(n−1)×…×3×2×1, and 0! = 1.
It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
How many, not necessarily distinct, values of  nCr, for 1 ≤ n ≤ 100, are greater than one-million?

Solution

HackerRank version

How many, not necessarily distinct, values of 5C3, for 1 ≤ n &le N, are greater than K?

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)	

Last Word

https://en.wikipedia.org/wiki/Digital_root