patternjavaModerate
Calculating count of square numbers between two numbers
Viewed 0 times
numberscalculatingbetweentwosquarecount
Problem
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.
What changes can be made to work efficiently on large numbers?
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?
Solution
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:
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;Code Snippets
return Math.floor(Math.sqrt(numberTwo)) - Math.ceil(Math.sqrt(numberOne)) + 1;Context
StackExchange Code Review Q#107114, answer score: 12
Revisions (0)
No revisions yet.