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