Teaching Kids Programming – Find the Integer Square Root (Brute Force Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since we round it down to the nearest integer, 2 is returned.

Constraints:
0 <= x <= 2^31 – 1

Find the Integer Square Root (Brute Force Algorithm)

Computing the square root of an integer is a classic problem in computer science and mathematics. Many efficient algorithms exist, such as Newton’s method or binary search, but one of the simplest approaches is the brute force algorithm. This blog post explores how brute force can be used to determine the integer square root of a given number.

A brute force algorithm iterates through all possible values of to find the integer square root. Here, we examine two implementations using Python.

Ascending Brute Force Search

1
2
3
4
5
6
7

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        for i in range(1, x // 2 + 1):
            if (i + 1) ** 2 > x:
                return i

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        for i in range(1, x // 2 + 1):
            if (i + 1) ** 2 > x:
                return i

Explanation:

• If x is 0 or 1, return immediately.
• Iterate from 1 up to half of x (since the square root of any number is at most half of it, except for small numbers).
• If the next number’s squared is greater than x, return current number as the integer square root.

Time Complexity: The loop runs at most x/2 times, making it relatively slow compared to other methods. Time complexity is O(N).

Descending Brute Force Search

We can search in the reverse direction.

1
2
3
4
5
6
7

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        for i in range(x, -1, -1):
            if (i - 1) ** 2 <= x:
                return i - 1

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        for i in range(x, -1, -1):
            if (i - 1) ** 2 <= x:
                return i - 1

Explanation:

• Again, return answer immediately if it is 0 or 1.
• Start iterating from down to 0.
• If the next number square is less than or equal to x, return it as the answer.

Time Complexity: This approach can be inefficient for large values of as it may iterate up to times, making it slower than the ascending search. Same time complexity O(N) – Linear.

The brute force approach to finding the integer square root is simple and easy to understand, but it is not the most efficient method. While the ascending search is slightly more optimized, both methods can be significantly outperformed by binary search or Newton’s method. If performance is a concern, consider using one of these advanced techniques instead.

–EOF (The Ultimate Computing & Technology Blog) —