# Find perfect squares in range [closed]

I've just taken the codility test on finding perfect squares in a range. I thought it was pretty straightforward, but on submitting, I got that a 50% on correctness and 66% on performance.

The spec also mentioned that range will be between [-2147483648 ... 2147483647], expected worst-case time complexity is O(sqrt(abs(B))) and expected worst-case space complexity is O(1).

This is my code:

## Solution1.java

public class Solution1 {

public int solution(int A, int B) {
int upperLimit = (int) Math.sqrt(B);
int squares = 0;
for (int i = 1; i <= upperLimit; i++) {
if (i * i >= A && i * i <= B) {
squares++;
}
}
return squares;
}
}


## Solution1Test.java

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class Solution1Test {

private final Solution1 solution1 = new Solution1();

@Test
public void given4_17_return3() {
assertEquals(3, solution1.solution(4, 17));
}

@Test
public void given1_17_return4() {
assertEquals(4, solution1.solution(1, 17));
}

@Test
public void given1_35_return5() {
assertEquals(5, solution1.solution(1, 35));
}

@Test
public void given1_36_return6() {
assertEquals(6, solution1.solution(1, 36));
}

@Test
public void given9_49_return5() {
assertEquals(5, solution1.solution(9, 49));
}

@Test
public void given3000_3300_return3() {
assertEquals(3, solution1.solution(3000, 3300));
}
}


I'm specially concerned (and confused) about the 50% on correctness.

PS: it this is off-topic just let me know and I'll ask on stackoverflow.

• "I'm specially concerned (and confused) about the 50% on correctness." What does that mean? Apr 22, 2018 at 21:30
• You tell us whether it fits all the criteria of on topic Apr 22, 2018 at 21:39
• @Raystafarian Why should this question not be on-topic? The author clearly stated that he thought the task was pretty straightforward and is therefore confused about receiving only 50% on correctness. Thus, the code works correctly to the best of the author's knowledge. Apr 22, 2018 at 23:27
• @Stingy the author mentioned they would remove it if it was not on topic, I was just providing a resource. I didn't vote to close Apr 22, 2018 at 23:31
• @Coal_ Thanks for letting me know. Having read the answer there, I don't fully understand why has my question been put on hold; I did add unit tests. Apr 30, 2018 at 8:39

The only reasons I can think of that your code was deemed incorrect are that it doesn't consider 0 as a perfect square, and that you don't consider the possibility that B < A (although maybe the test defined B as being greater than or equal to A and this is not a negligence of you). As for the performance, here are some suggestions:
• You don't need to check i * i <= B in the loop, because the termination condition of the for loop already required that i <= upperLimit, and with i being positive, there is no way that i*i > B if i <= sqrt(B).
• Taking the above into account, it follows that once the loop reaches an i for which i * i >= A, there is no point in continuing the loop, because all future values of i will have squares that fall within the specified range.
• Continuing this trail of thought, it turns out that the solution can simply be expressed as (int) (Math.floor(Math.sqrt(B)) - Math.ceil(Math.sqrt(Math.max(A, 0)))) + 1, provided B is non-negative and B >= A. This expression doesn't really do anything your code doesn't do except floating point arithmetics. I don't know if two calls to Math.sqrt() (which delegates to StrictMath.sqrt(), which is a native method) are faster than using integer arithmetics in a loop, but it's definitely more to the point, coding-wise.