Project Euler 9: Special Pythagorean triplet

Problem

A Pythagorean triplet is a set of three natural numbers, a < b < c , for which,a² + b² = c²

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

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

Solution Approach

In this problem of Special Pythagorean triplet, we have to find three number which forms Pythagorean triplet. The numbers should be such that they add up to 1000. We have to find the product of the three numbers as the answer.

We can use a brute force algorithm to solve the problem. The maximum number that we have to search for is bounded by 2*(1000²) which fits the integer data type. We can start with giving one value to a, then giving subsequent values to b, and finding c by subtracting values of a and b from 1000. Then we place these in Pythagoras equation to find if they are Pythagorean triplet or not.

The time complexity of this approach is O(n²) as we have to iterate through 1 to 1000 twice for a and b. The space complexity of this approach is constant i.e O(1) as we are just using a variable to store the value of the product.

Coming to the code, we run two loops. The outer loop will initialize values of a from 1 to 1000. The inner loop will be used for values of b. C’s value can be calculated by the equation 100-a-b. Secondly, we test if a,b,c are Pythagorean triplets. Lastly, if they are then we calculate the product and return that value as the answer.

Solution Code

Java Solution

class Solution
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    int LIMIT = 1000;
		for(int a=1; a<=LIMIT; a++){
		    for(int b=a+1; b<=LIMIT; b++){
		        int c = LIMIT-a-b;
		        if(a*a + b*b == c*c){
		            System.out.println(a*b*c);
		            return;
		        }
		    }
		}
	}
}

class Solution

{

public static void main (String[] args) throws java.lang.Exception

{

int LIMIT = 1000;

for(int a=1; a<=LIMIT; a++){

for(int b=a+1; b<=LIMIT; b++){

int c = LIMIT-a-b;

if(a*a + b*b == c*c){

System.out.println(a*b*c);

return;

}

Python Solution

LIMIT = 1000

for a in range(1, LIMIT):
    for b in range(a+1, LIMIT):
        c = LIMIT - a - b
        if (a**2 + b**2 == c**2):
            print(a*b*c)
            break

LIMIT = 1000

for a in range(1, LIMIT):

for b in range(a+1, LIMIT):

c = LIMIT - a - b

if (a**2 + b**2 == c**2):

print(a*b*c)

break

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding 🙂

Problem

Solution Approach

Solution Code

Java Solution

Python Solution

Leave a Comment Cancel Reply