I based my solution on Euclid’s formula for generating Pythagorean triples.
And given that max L is 1,500,000, the maximum value for m we need to consider is . Because and , we can deduce that ; and since we also have and therefore .
The above makes use of a recursive function to calculate the GCD (based on Euclidean Algorithm):
For efficiency, we’ll create a cache to store the number of ways L can be used to create integer sided right-angle triangle. As we iterate through the m and n pairs we generated above, we’ll take advantage of the fact that if then must also be true and increment multiples of L by one.
Finally, to work out the answer:
This solution runs for about 350ms on my machine.
The source code for this solution is here.
I’m an AWS Serverless Hero and the author of Production-Ready Serverless. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.
Here is a complete list of all my posts on serverless and AWS Lambda. In the meantime, here are a few of my most popular blog posts.
- Lambda optimization tip – enable HTTP keep-alive
- You are thinking about serverless costs all wrong
- Many faced threats to Serverless security
- We can do better than percentile latencies
- I’m afraid you’re thinking about AWS Lambda cold starts all wrong
- Yubl’s road to Serverless
- AWS Lambda – should you have few monolithic functions or many single-purposed functions?
- AWS Lambda – compare coldstart time with different languages, memory and code sizes
- Guys, we’re doing pagination wrong