Project Euler 9 Solution

Project Euler Problem 9 Solution & HackerRank version

Special Pythagorean triplet

by {BetaProjects} | MAY 9, 2009 | Project Euler & HackerRank

Project Euler Problem 9 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

A Pythagorean triple consists of three positive integers a, b, and c, such that a < b < c and a2 + b2 = c2. These triples are commonly written as (a, b, c), and a typical example is (3, 4, 5); 32 + 42 = 52 or 9 + 16 = 25.

A primitive Pythagorean triple is one in which a, b and c are coprime (that is, gcd(a, b, c) = 1; they have no common factors between them) and for any primitive Pythagorean triple a non–primitive Pythagorean triple can be calculated as: (ka, kb, kc) for any positive integer k > 1.

Having solved this problem for a target sum of 1000 was pretty easy, but HackerRank has us run thousands of test cases for any target sum ≤ 3000. That was a bit more challenging.

An iterative approach

We are given the target sum, N, so this is our independent variable. It can assume any value, such as 1000 in this particular case. a, b, c are our dependent variables as we must somehow derive them through iteration. If we can reduce our iterative search to one independent variable and one dependent variable, then this solution would yield an O(N) algorithm.

Well, c is easy – we can define it in terms of a, b and n as:

Solving for c

Now, with c out of the way, and through some algebraic magic, we can solve for b in terms of a and n. We only need one loop for a and can calculate b:

Solving for c

(1) Use our new definition for c
(2) Expand the right–hand side
(3) Isolate the b terms on the left
(4) Factor both sides of the equation
(5) Solved for b in terms of a and n

A few optimizations

As expected, this algorithm worked to solve this problem and the HackerRank version within the time constraint.

HackerRank version

HackerRank requires us to run 3,000 test cases for 1 ≤ N ≤ 3000. As there could be more than one Pythagorean triplet that exists for the target sum, print the one with a maximum possible product of a, b and c. Print −1 if none are found.

Python Source Code

  1. n = int(input("The Pythagorean triplet that sums to "))
  2. p = -1; trip = "None."
  3. for a in range(n//3-1, 2, -1):
  4. b = n*(n-2*a) // (2*(n-a))
  5. c = n - a - b
  6. if a<b and a*a + b*b == c*c: p = a*b*c; trip=(a,b,c); break
  7. print ("is",trip," product =",p)

Last Word