0
\$\begingroup\$

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.

\$\endgroup\$

closed as off-topic by 200_success, t3chb0t, Daniel, Sᴀᴍ Onᴇᴌᴀ, Dannnno Apr 28 '18 at 19:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – 200_success, t3chb0t, Daniel, Sᴀᴍ Onᴇᴌᴀ, Dannnno
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ "I'm specially concerned (and confused) about the 50% on correctness." What does that mean? \$\endgroup\$ – πάντα ῥεῖ Apr 22 '18 at 21:30
  • 1
    \$\begingroup\$ You tell us whether it fits all the criteria of on topic \$\endgroup\$ – Raystafarian Apr 22 '18 at 21:39
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Stingy Apr 22 '18 at 23:27
  • \$\begingroup\$ @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 \$\endgroup\$ – Raystafarian Apr 22 '18 at 23:31
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – antonro Apr 30 '18 at 8:39
6
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.