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