Friday, June 14, 2013

[Project Euler] Problem 9 in C

Problem: Project Euler Problem 9

Algorithm
I decided to approach this problem at more mathematical angle because without doing so, the program will need to iterate through 2 variables instead of 1 variable to arrive at an answer, drastically reducing the runtime.

Optimization
A relationship between two variables has been found on paper through algebra, so, O(n) was achieved instead of O(n^2).

a + b + c = 1000   ...   (1)
a^2 + b^2 = c^2   ...   (2)

Solving a^2 + b^2 = (1000-a-b)^2,
a = 1000 + 500,000 / (b - 1000)   ...   (3)

Iterate through b to solve for a. If a is a natural number, then we have arrived at our solution.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int b = 1, c = 1;
    float a=0;

    for (b = 1; b < 998; b++ ){
        a = 1000.0 + 500000.0/(b-1000.0);
        if ( a == (long)a)    // Check for integer max and min for general use to check if integer
            break;
    }

    c = 1000 - a - b;
    printf("%f\n", a*b*c);
    return 0;
}


Best Execution Time: 0.006s
Answer:

No comments:

Post a Comment