Count number of square integers in a given range of ints (faster function?)

Question

The function below passes most test cases:

function numOfSquares(a, b) { 
 const isSquare = function (n) {
 return n > 0 && Math.sqrt(n) % 1 === 0;
 };
 let squareCount = 0;
 for (let i = a; i <= b; i++){
 if (isSquare(i)) {
 squareCount++;
 }
 }
 return squareCount
}

numOfSquares(3, 9) //out: 2 numOfSquares(17, 24) //out: 0

The time complexity of this is O(n)... right?

The problem is that this function does not pass the test cases being provided due to the time complexity. For example, in one case, the input could be numOfSquares(465868129, 988379794) (expected out: 9855). In my case, using the function above, it seems to run... forever.

How can I make this function more efficient, and thus faster?

Answer 1

You are correct that your solution is O(n). However, there is a possible solution for O(1). If you find the root of the first square (first) and the last square (last), then all of the numbers between first and last will yield squares in the range.

function numSquares(min,max) {
 const first = Math.ceil(Math.sqrt(min));
 const last = Math.floor(Math.sqrt(max));
 return last-first+1;
}
console.log(numSquares(465868129, 988379794));