# Project Euler #91 – Java

You can see the problem here: Problem #91.

This problem is pretty easy.

As you can see from the first pictures, if both coordinates are located at the sides of the grid, we can make a right triangle. That right triangle can also be transformed into two other right triangles, as seen from the remaining two triangles. Since there 50 * 50 = 2500 ways to choose those two coordinates, we already know there are at least 2500 * 3 = 7500 right triangles. Now we just need to figure out a way to find the rest of the triangles.

Let’s say we want to find a right triangle with coordinate *P* = (1, 2). If we draw a line starting from the origin *O* to *P*, the line will have a slope of 2. Then if we draw a line with a slope -1/2, the negative reciprocal of 2, it will be perpendicular to *OP*. Since the other coordinate *Q* needs to contain integers, we will find *Q* by moving *P* 2 blocks to the right and 1 block down (using slope = -1/2 and definition of slope). See the pictures below for a more visual explanation. The red line has a slope of 2 (1 block right, 2 blocks up) and the blue line has a slope of -1/2 (2 blocks right, 1 block down).

The above right triangle can also be reflected along the line y = x to make another right triangle.

Also, we can extend *PQ* another 2 blocks to the right and 1 block down and make a different right triangle.

There is one last thing to note about. Let’s say the *P* coordinate is (2, 4), the negative reciprocal of its slope would be -2/4. We need to simplify -2/4 to -1/2 before we can use it in the algorithm, or else we can miss some right triangles. Taken all the above points into account, here is the code (surprisingly short for a Project Euler problems):

final int SIZE = 50; int answer = SIZE * SIZE * 3; for (int x = 1; x <= SIZE; x++) { for (int y = 1; y <= SIZE; y++) { int gcf = EulerMath.GCF(x, y); //bunch of small utility methods I kept in EulerMath int dx = x / gcf; int dy = y / gcf; answer += Math.min(y / dx, (SIZE - x) / dy) * 2; } } System.out.println(answer);

Runs in ~3 milliseconds on my computer. Note that the problem can also be easily brute force due to its small size, oh well. CU

## Leave a Reply