[C/C++] Project Euler #53 - Combinatoric Selections

This problem is a simple one. As long as you know the combination formula, it’s easy to solve.

When n varies from 1 to 100, you need to calculate the number of times the combination value \(_nC_r\) exceeds one million.

Even with a brute-force approach, you only need to compute combinations 10,100 times.

If you know that \(_nC_r = nC{n-r}\), you can reduce the calculations by half. Because of its symmetrical nature and the simple increase/decrease pattern, you can reduce the number of computations even further.

However, since the number of multiplications required for calculating combinations increases, the actual time complexity would be about \(O(n^3)\). Since n only goes up to 100, it just takes a bit more time—not so much that it becomes impossible.

I solved the problem using a slightly unconventional approach.

I used Pascal’s Triangle.

 

As you can see in the diagram above, the left and right edges of the triangle are filled with 1s. The values inside the triangle are calculated using the sum of the two adjacent values directly above.

I used this principle to store the values corresponding to each n in an array and used those values to find the numbers.

For example, if we’re talking about the 4th row, the array would contain:

1 3

And next, I build the next row using the values from the previous one:

1 4 6

---

combinations

Here is the source code I wrote:

//------------------------------------------------
//    Project Euler #53 - Combinatoric Selections
//        - by Aubrey Choi
//        - created at 2015-03-31
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

int GetCombination(int n, int r);

int main()
{
    int combs[20];

    for( int i = 0 ; i <= 10 ; i++ )
    {
        combs[i] = GetCombination(23, i);
        printf("C(%d, %d) = %d\n", 23, i, combs[i]);
    }

    int first = 10;
    int n = 23;
    int count = n+1-first*2;
    for( n++ ; n <= 100 ; n++ )
    {
        for( int i = first-1 ; i > 0 ; i-- )
        {
            combs[i] += combs[i-1];
            if( combs[i] > 1000000 ) first = i;
        }
        count += n+1-first*2;
    }
    printf("ans = %d\n", count);
}

int GetCombination(int n, int r)
{
    int c = 1;
    for( int i = 0 ; i < r ; i++ ) { c *= n-i; c /= i+1; }
    return c;
}