The problem 91 of Project Euler was a bit tricky. It requires one to find the number of right angled triangles in a n X n grid, with one point 
fixed. For example, as shown on the problem page, a 3 X 3 grid contains 14 triangles. The problem required the answer for a 51 X 51 grid.
Well, at first I started with a pencil-paper approach. I listed down all the cases I could think of and checked my calculation for the 3 X 3 grid. Got the answer right. But applied the same to the larger 51 X 51 grid I realized that there were cases I had not enumerated all the cases. I am still not sure if the problem can be solved using just a pencil and a paper.
I did not want to do a brute force way of picking up two arbitrary points and checking if they form a right angled triangle. In my solution I have never tried to determine the actual triangles. As you shall see, all I do is to find the number of possible triangles by using a parameter and bounding it within an interval. The range of the interval is my solution for that particular point.
I went the mathematics way. One of the points is fixed at . Select one point as 
. The slope of the line joining these two points is 
. So the equation of a line perpendicular to this one and passing through the point would be :
Now points which lie on the above line will all form right angled triangles with the points and . The following conditions need to be satisfied in our particular problem:
- The solutions to the above equation are integers.
- The points lie within a grid of n X n. So
and 
.
There are two cases we need to consider. One where 
is a multiple of 
and the other where it is not.
Let us first consider the case where is not a multiple of . We rewrite the equation as follows:
where 
is the gcd of and . Now since 
is an integer, we can impose the following condition on 
:
where k is some parameter, in which case the value of becomes:
And now imposing the second criteria, we can limit the values of the parameter 
as thus:
Similarly, imposing the same conditions for , we get
The intersection of the two intervals gives us the eligible values for the parameter as :
For 
we get the point . For all other values of we get the points which complete the right angled triangle. So the number of right angled triangles in this case will be the range of k – 1.
Now the other case. Let 
. The equation then becomes :
Let 
. Then we have
Once again the applying the boundary conditions we get:
Once again taking the intersection of the intervals gives us:
For we get the point . For all other values of we get the points which complete the right angled triangle. So the number of right angled triangles in this case will be the range of k – 1.
Add to this the trivial case of 
right angled triangles formed when one of the points lie on the axis. It is easy to see these if you sit with a pencil and a paper.
I went ahead to code the above conditions. The code is given below. On my laptop I was able to run this code for a grid of 4000 X 4000 in 1 second.
In the code given below, I have used 
as the point . and 
are as described above.
public int getCount(int n) {
int count = 0;
for (int xIdx = 1; xIdx <= n; xIdx++)
for (int yIdx = xIdx; yIdx <= n; yIdx++) {
int tempCount = xIdx % yIdx == 0 ? countForXMultipleOfY(xIdx, yIdx, n) : countForXNotMultipleOfY(xIdx,
yIdx, n);
count += xIdx != yIdx ? 2 * tempCount : tempCount;
}
return (int) (count + 3 * Math.pow(n, 2));
}
private int countForXMultipleOfY(int xIdx, int yIdx, int n) {
int p = xIdx / yIdx;
int lowerBoundary = NumberUtil.larger((yIdx - n) / p, xIdx * -1);
int upperBoundary = NumberUtil.smaller(yIdx / p, n - xIdx);
return upperBoundary > lowerBoundary ? upperBoundary - lowerBoundary : 0;
}
private int countForXNotMultipleOfY(int xIdx, int yIdx, int n) {
int f = MathUtils.gcd(yIdx, xIdx);
int lowerLimit = NumberUtil.larger(-1 * xIdx / (yIdx / f), (yIdx - n) / (xIdx / f));
int upperLimit = NumberUtil.smaller(yIdx / (xIdx / f), (n - xIdx) / (yIdx / f));
return upperLimit > lowerLimit ? upperLimit - lowerLimit : 0;
}
Popularity: 16% [?]
