Combinatoric selections is problem #53 on Project Euler. The problem statement is as follows.
There are exactly ten ways of selecting a combination of three from five numbers, 12345:
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
In combinatorics, we use the notation ${5 \choose 3} = 10$.
In general, ${n \choose r} = \frac{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: ${23 \choose 10} = 1144066$.
How many not necessarily distinct values of ${n \choose r}$ for $1 \le n \le 100$ are greater than one million?
#include <iostream> #include <vector> using namespace std; int main() { unsigned long long count = 0; int n = 23; unsigned long long k = 1000000; vector<vector<unsigned long long>> pascalsTriangle(n+1); for(int i = 0; i <= n; i++){ for(int j = 0; j<= i; j++){ if(i == 0 || j == i || j == 0){ pascalsTriangle[i].push_back(1); } else{ pascalsTriangle[i].push_back(pascalsTriangle[i-1][j-1] + pascalsTriangle[i-1][j]); if (pascalsTriangle[i][j] >= k){ count++; pascalsTriangle[i][j] = k; } } } } cout << count << endl; return 0; }
The problem is quite simple. All we are required to do is calculate ${n \choose r}$ for $2 \le n \le N$ and return the count of the number of values above a certain threshold, $K$.
The naive approach is to calculate the value of ${n \choose r}$ using the formula provided in the problem statement. However, that approach, while correct, is slow and inefficient. Moreover, it suffers from integer overflows when calculating the factorials and can give inaccurate results.
A much better approach is to generate Pascal’s triangle. This method is faster because it only uses the addition operation instead of having to calculate large factorials and then perform multiplication and division operations on them.
We generate Pascal’s triangle in the main for
loop. There are three conditions for which we fill a slot with $1$:
If the row index is 0, meaning we are at the topmost block.
If the column index is 0, meaning we are at the beginning of a row.
If the column and row index are equal, meaning we are at the end of a row.
We deal with these three conditions in the following code snippet:
if(i == 0 || j == i || j == 0){
pascalsTriangle[i].push_back(1);
}
For the rest of the slots, we use the slots above them and add them together to get the value of the new block. The slots that we use are the ones directly above the new block, at position [row - 1][columns]
and the one adjacent to it at position [row - 1][columns - 1]
.
The most important part is in the last if
condition. We check if the new number is greater than or equal to $K$, and if so, we increment the count. An important step is to set the number to $K$ as well. This will prevent integer overflow errors for large values of $N$.
RELATED TAGS
CONTRIBUTOR
View all Courses