GDC Project Euler: problem 108 – Jaroslaw Pawlak

  • Difficulty: rather difficult

  • First solution:

My first solution was as usually a brute one. The algorithm was decreasing x and increasing y depending on the difference between 1/x + 1/y and 1/n. It was starting from x = y = 2n and if 1/x + 1/y = 1/n then was both decreasing x by one and increasing y by one. If 1/x + 1/y > 1/n then only y was increased. In the last case only x was decreased. Although the algorithm worked, it was extremely slow. Code below:

private static int solutions(int n) {

int result = 0;
int x = n * 2;
int y = n * 2;
while (x > n) {

if (n * (x+y) == x * y) {

result++;
x–; // x -= 1, displayed incorrectly by the forum…
y++;

} else if (n * (x+y) > x * y) {

y++;

} else {

x–;

}

}
return result;

}

I have spot that for given x and n, there exists exactly one y and is equal to nx/(x-n). If the value is an integer (in other words, if a remainder == 0), then we get one more distinct solution for given n. So the second algorithm looked as follows:

private static int solutions(int n) {

int result = 0;
int x = n * 2;
while (x > n) {

if ((n * x) % (n – x) == 0 ) {

result++;

}
x–;

}
return result;

}

This solution worked much faster but even though n < x < 2n, y is increasing much faster than x is decreasing and results in overflow of y. Changing the values to long did not solve the problem, while using BigInteger class has greatly increased computation time, making an algorithm unable to find n, for which there are at least 1000 distinct solutions.

  • Techniques used:

Java program with simple mathematical algorithm.

  • How much time did it take:

First solution has been written in about thirty minutes, but was unable to find an answer. Second solution was implemented in another thirty minutes, but was also unable to find an answer. Third solution was implemented in about an hour and found an answer in 1 minute and 53 seconds.

All together I spent on this problem about 2 hours in two days.

My final solution was implemented after further observations of connectives between x and y. I have spotted that x = n + a, where 1 <= a <= n, and then y = n(n+a)/a. To obtain a distinct solution, y must be an integer. Because a is always divisible by a, it is enough that n^2 is divisible by a. So for every integer from 1 to n (both sides inclusive) if n^2 is divisible by a, then we have one more distinct solution:

private static int solutions(long n) {

 int r = 0;
for (int i = 1; i <= n; i++) {

if ((n * n) % i == 0) {

r++;

}

}
return r;

}

This code bases only on mathematical observations and is not optimized at all. For sure it will not be able to find an answer for the problem 110.

  • Problems encountered:

Complex and redundant computations was slowing the algorithm down.

  • What I have learned:

I have learned that if something takes too much time, I should focus not on optimizing computations, but on making observations and looking for a different approach to the problem. It may help me to solve the problem 338 I am still struggling with.

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

Posted on June 11, 2011, in GDC Project Euler Challenge, Project Euler. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: