Wilson Tan Wilson Tan - 2 months ago 5
Java Question

Maximum value of int breaking my for loop?

I was attempting to solve this morning's Codeforces problem Div 2C: http://codeforces.com/contest/716/problem/C

This problem has the potential to loop up to 100,000 times so the parameter here can be up to 100,000. Loop seems to break when passing in 100,000 (and possibly earlier) and i is declared as an int:

public void solve(int a) {
double x = 2;
double y = 0;
double n = 0;
double target = 0;
double lcm = 0;
for (int i = 1; i <= a; i++) {
lcm = (i + 1) * i;
y = ((lcm * lcm) - x) / i;
n = (y * i) + x;
if (Math.sqrt(n) % (i + 1) == 0) {
x = Math.sqrt(n);
String answer = String.format("%.0f", y);

System.out.println("this is i: " + i);
System.out.println(answer);

}
}
}


Here is the relevant output:

this is i: 46337
99495281029892
this is i: 46338
99501722706961
this is i: 46340
99514606895203
this is i: 65535
32769


Doing a quick search on Stack overflow shows that the number 65535 is associated with a 16-bit unsigned int, but java uses 32bit ints. Changing the type to double works, as does simply looping 100,000 times and printing without the code logic. I understand that 100,000^2 IS above the maximum int limit, but this value is never stored as an int in my code. What's going on here?

Answer

The following line generates an out of bounds int before converting the result to double:

lcm = (i + 1) * i;

The above is essentially the same as:

lcm = (double)((i + 1) * i);

or

int temp = (i + 1) * i;
lcm = (double) temp;

Instead try (first converting to double and then taking what is similar to a square):

lcm = (i + 1.0) * i;
Comments