5
\$\begingroup\$

The problem is to find out the squares between two numbers, inclusive of the numbers. The two numbers are in the range between 1 and 109.

long numberOne = in.nextLong();
            long numberTwo = in.nextLong();
            int count=0;
            for(long j=numberOne;j<=numberTwo;j++){
                double numSquareRoot=Math.sqrt(j);
                double numFloor=Math.floor(numSquareRoot);
                if(numSquareRoot == numFloor) count++;
            }

What changes can be made to work efficiently on large numbers?

\$\endgroup\$

1 Answer 1

Reset to default
12
\$\begingroup\$

Can be done in \$O(1)\$ time

The count should be:

\$\lfloor{\sqrt n}\rfloor -\lceil{\sqrt m}\rceil + 1\$

or in terms of your program:

return Math.floor(Math.sqrt(numberTwo)) - Math.ceil(Math.sqrt(numberOne)) + 1;
\$\endgroup\$
1
  • \$\begingroup\$ I'm not math background. Mind to explain as simple as you could how you get this? And whats that O(1) time? What topic/subject is that? \$\endgroup\$ Commented Jun 3, 2016 at 0:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.