Post date: Nov 16, 2014 11:21:23 PM
"There is a somewhat involved setup for this problem, but it doesn't matter. How many values of the following formula, where n is between 1 and 100 inclusive and r is less than or equal to n, provide results over 1 million: n! / r! * (n - r)!"
In the bottom half, the numbers in r! all cancel out one or more numbers in n! in the top, which greatly reduces the number of calculations we need to do. But better yet, we only care about if the result is over 1 million. We don't care about all the significant digits. So the float data type is fine. So this is a nice single-query answer.
-- Fact1 is the top factorial (partial) and fact2 is the bottom factorial. Fact2 doesn't include r! and fact1 only considers the results where n is greater than or r (the others were cancelled).
WITH Hundred (i) AS
(
SELECT 1
UNION ALL
SELECT i + 1
FROM Hundred
WHERE i < 100
)
SELECT COUNT(*)
FROM Hundred n
INNER JOIN Hundred r
ON r.i <= n.i
CROSS APPLY (
SELECT EXP(SUM(LOG(i)))
FROM Hundred fact
WHERE fact.i <= n.i
AND fact.i > r.i) fact1 (i)
CROSS APPLY (
SELECT EXP(SUM(LOG(i)))
FROM Hundred fact
WHERE fact.i <= n.i - r.i) fact2 (i)
WHERE fact1.i / fact2.i > 1000000