Find perfect squares in range

2018-04-22 23:43:36

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.so

  • 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

    2018-04-23 02:03:30