**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}.

Related Tags:

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(n ^{2})` to

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:

`a ^{2} + b^{2} = c^{2}`

Equation 2

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

`b = (p ^{2} - 2pa) / 2(p - a)`

Equation 3

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.

```
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!

Next Challenge: Rotate a 2d array in place