Special Pythagorean triplet: Project Euler Problem 9

Problem link: http://projecteuler.net/problem=9

Problem Statement:
A Pythagorean triplet is a set of three natural numbers, a<b<c, for which,
a^2+b^2=c^2.

For example, 3^2+4^2=9+16=25=5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.


Solution Idea:
We have 3 variables a,b,c. So, We need at least 3 equations to solve them in constant time. But, we are given 2 equations: a+b+c=n and c^2=a^2+b^2. So, we combine these 2 equations and can get rid of c, (n-a-b)^2=a^2+b^2, which will simplify to b={{n^2-2na}\over{2n-2a}}. Now we can iterate through all possible values of a and find the solution in linear time.

Solution Gist:

Advertisements

Tagged: , , , , ,

5 thoughts on “Special Pythagorean triplet: Project Euler Problem 9

  1. Alumashka November 28, 2013 at 1:28 am Reply

    However, with limitation “a + b + c = 1000” even O(N^2) solution would work less than a second.

    It would be interesting extend the problem for far greater numbers…

  2. Faisal R. November 28, 2013 at 6:54 am Reply

    yes , for sure. ๐Ÿ™‚

  3. Alumashka at CodeAbbey November 30, 2013 at 5:28 am Reply

    Hello, Faisal!

    I tell about this task and your explanations to my friend and asked him, whether he can create an improved version of the problem at his web-site. He agreed to try.

    See, here it is:

    http://codeabbey.com/index/task_view/pythagorean-triples

    The numbers there would be greater, over million, so that solution could be found only by your method, not by simply iterating over a and b… ๐Ÿ™‚

    Wouldn’t you mind mentioning you as a person who gives idea? If so, please check if your name is spelled correctly. Thanks a lot once more!

    • Faisal R. December 1, 2013 at 9:20 pm Reply

      I am honored, thank you ๐Ÿ™‚

  4. atiq September 30, 2014 at 8:42 pm Reply

    Thank you Faisal…for very clean approach.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: