Find perfect squares in range [closed]

Question

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.

Answer 1

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.