Project Euler 114 and 115

Question

I am having a problem with project euler problem 114. I have solved problem 115. Isn't 114 just F(3, 50)? I used Combination method instead of the popular recursive one. I don't understand why Q114 cannot be solved.

Question 114

Question 115

unsigned long long Q114::nCr(unsigned long long n, unsigned long long r) {
    unsigned long long result = 1;
    for(unsigned long long i = 1; i <= r; i++)
        result *= (n--);
    while(r != 1)
        result /= (r--);
    return result;
}

unsigned long long Q114::find(unsigned long long leastunit, unsigned long long total) {
    unsigned long long max = (total + 1) / (leastunit + 1);
    unsigned long long sum = 0;
    for(unsigned long long i = 1; i <= max; i++) {
        unsigned long long slots =  2 * i;
        unsigned long long left = (total - i * leastunit - (i - 1));
        sum += nCr(left + slots, slots);
    }
    return sum;
}

void Q114::solve() {
    unsigned long long sum = find(3,50);
    std::cout << (++sum);
}

void Q114::solveQ115() {
    for (long start = 50;;++start) {
        std::cout << start << std::endl;
        if(find(50, start) > 1000000) { 
            std::cout << start << std::endl;
            break;
        }
    }
}

Thanks!

Answer 1

I changed your code to 'big number' version, then I got the right answer 16475640049.

I think the reason lies in this sentence:

result *= (n--);

The value of 'result' will overflow here.

'unsigned long long' is not enough for storing the result.

Update:

Since you've got where's the problem, we can fix this by simply changing the code as below:

unsigned long long Q114::nCr(unsigned long long n, unsigned long long r) {
    unsigned long long result = 1;
    for(unsigned long long i = 1; i <= r; i++)
    {
        result *= (n--);
        result /= i;  // highlight
    }
    return result;
}

You may have a try with this solution.