3
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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