Square Root Integral in Python

Given a number N, find its square root. You need to find and print only the integral part of square root of N.

For eg. if number given is 18, answer is 4.

Input format :

Integer N

Output Format :

Square root of N (integer part only)

Constraints :

0 <= N <= 10^8

Understanding the Problem: Given a non-negative integer ‘N’, our objective is to find and print only the integral part of its square root. In other words, we’re interested in the largest integer whose square is less than or equal to ‘N’.

Binary Search Approach: To efficiently find the integral square root, we’ll leverage the binary search algorithm. We’ll define a search space from 1 to ‘N’ and iteratively narrow down the search range until we find the integral square root.

Algorithm Overview:

1. Initialize the search range from 1 to ‘N’.
2. Use binary search to iteratively divide the search range.
3. At each iteration, compute the square of the middle element (‘mid’) of the search range.
4. If the square of ‘mid’ equals ‘N’, ‘mid’ is the integral square root.
5. If the square of ‘mid’ is less than ‘N’, update the lower bound of the search range to ‘mid + 1’ and store ‘mid’ as the potential integral square root.
6. If the square of ‘mid’ is greater than ‘N’, update the upper bound of the search range to ‘mid – 1’.
7. Repeat steps 3-6 until the search range is exhausted.

Python Implementation

def square_root_integral(N):
    # Base cases
    if N == 0 or N == 1:
        return N

    # Binary search to find the integral part of square root
    start, end = 1, N
    result = 0
    while start <= end:
        mid = (start + end) // 2
        square = mid * mid

        # If mid is the integral square root
        if square == N:
            return mid
        # If mid^2 is less than N, update result and search in the right half
        elif square < N:
            start = mid + 1
            result = mid
        # If mid^2 is greater than N, search in the left half
        else:
            end = mid - 1

    return result

# Main function
if __name__ == "__main__":
    N = int(input().strip())  # Read input number
    print(square_root_integral(N))  # Print integral part of square root