For this practice I completed problem 1.19 from the Data Structures and Problem Solving using Java book. This book is a bit old, but is still a great resource for brushing up on Java and solving some interesting problems (and the best part being that I already owned it :) ). Of course, all of the source code for the problem is available on Github
Write a program to determine all pairs of positive integers (a,b) such that a < b < 1000 and (a2+b2+1)/(ab) is an Integer.
This was a pretty simple problem, pretty much just:
- Loop up to 1000 setting value to
- Loop up to the current value of
bsetting the value to
- Run the calculation (a2+b2+1)/(ab) for current values of
- Check if the current value from the calculation is an integer using a cast and compare with the current value.
Because the solution requires us to loop through all values for
a up to
b and all values of b up to 1000 the loop will always be exhaustive. The check for whether
this value is an integer is negligible in comparison to these loops so it does not need to be factored in for worst case analysis. This results
in us having a Big O performance of O(n2) or quadratic. This is not the greatest runtime in the world since the runtime will increase pretty rapidly if
we were to increase the maximum number for the value (in this case 1000).
Thats all for now, happy coding!