# Integer Right Triangles

Question:
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120: {20,48,52}, {24,45,51}, and {30,40,50}.

## Brute force

We could write a triple for-loop and try out all possible values for a, b and c, but with a little math we can reduce this complexity from O(n2) to O(n2).

## Writing out the math

Before we jump straight into coding, let's write out some math.

We know that the total perimeter is p, so we can write:

a + b + c = p

Equation 1

Furthermore, we know from the pythagorean theorem that this equation holds true for right triangles:

a2 + b2 = c2

Equation 2

Now if we plug in c = p - (a + b) into the Pythagorean theorem, we get:

b = (p2 - 2pa) / 2(p - a)

Equation 3

## More analysis

Consider the following scenarios and correlaries.

a and b are even
c is even by Equation 2, and p is even by Equation 1.
a and b are odd
c is even by Equation 2, and p is even by Equation 1.
a or b is odd (not both)
c is odd by Equation 2. In this case, p is still even.

Thus we know that p is even, so we only need to check every other p.

Furthermore, we can say that a < c and b < c and a <= b < c (we can switch a and b around as needed. Thus, we know that a is at most p/3 from Equation 1.

## Implementation in Java

public class IntegerRightTriangles {
public static void main(String[] args) {

System.out.println(maxNumPossible(1000));

}

static int maxNumPossible(int upperBound) {

// max number of possible values
int numMax = 0;
// maximum value for p
int maxIndex = 0;

for (int p = 3; p <= upperBound; p +=2) {

// number of possible values for this i
int numPossible = numPossible(p);

if (numPossible > numMax)  {
numMax = numPossible;
maxIndex = p;
}
}

return maxIndex;

}

static int numPossible(int p) {

int numPos = 0;

for (int a = 2; a < p/3; a++) {

// Only integer values
if ((p*p - 2*p*a) % (2*(p-a)) == 0 ){
numPos++;
}

}

return numPos;
}

}

Came up with a better solution or have a question? Comment below!