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.
nCr = n! / (r!(n-r)!)
where r <= n, 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?
At first I looked at this and thought it was all about iterating through the combinations of digits, just like how it lists 123, 124, etc. Which sounds tricky. But it’s much simpler than that. In fact they give you the hardest part of the algorithm, the equation needed:
n! / (r!(n-r)!)
In Python this solution takes about 0.36 seconds. I’m going to start using the time module to calculate running times.
import time tStart = time.time() values = 0 def factorial(x): y = 1 for i in range(1,x+1): y = y * i return y def calc(n, r): return factorial(n) / (factorial(r) * factorial(n-r)) for i in range(1,101): for j in range(1, i): if calc(i, j) > 1000000: values += 1 print(values) print("time:" + str(time.time() - tStart))
So, two functions, one calculates the factorial of x, the other just calculates our equation. The second function could instead have just been expressed as one line in our procedural code.
Then loop from 1 to 100. Within that, do an inner loop from 1 to whatever our current outer loop is on, passing the two loop counters into our function. We don’t really care which numbers produce values greater than a million; we only care how many numbers there are. So value is just a simple counter.