Lecture Notes: Finding the Square Root of X

Introduction

• Problem: Given a non-negative integer X, return the square root of X rounded down to the nearest integer.
• Example:
  • Square root of 4 = 2
  • Square root of 8 ≈ 2.82, return 2.

Brute Force Approach

• Start with an integer X, e.g., X = 7.
• Iterate from 1 to X:
  • Check if the square of the current integer equals X.
  • For 1: 1² = 1 (too low)
  • For 2: 2² = 4 (still too low)
  • For 3: 3² = 9 (exceeds X, stop)
• Result: The largest integer whose square is less than or equal to X is returned, which is 2 for X = 7.

Complexity of Brute Force

• Although it seems O(n), it actually terminates at the square root of n.
• Time complexity: O(√n).

Optimized Approach: Binary Search

• More efficient method with time complexity O(log n).
• Rationale:
  • Compare performance of √n vs. log₂n with large values, e.g., n = 1,000,000
  • √1,000,000 = 1000
  • log₂(1,000,000) ≈ 20
• Logarithmic growth is much slower than square root growth.

Steps for Binary Search

1. Initialize search space:
   • Left = 0
   • Right = X
   • Result = 0 (initial value)
2. While left ≤ right:
   • Calculate mid:
     • mid = left + (right - left) // 2 (avoids overflow)
   • Check conditions:
     • If mid² > X:
       • Update right = mid - 1 (search left)
     • If mid² < X:
       • Update left = mid + 1 (search right)
       • Update result = mid (potential candidate)
     • Else:
       • Return mid (exact square root found)
3. Return result after the loop, which will be the largest mid where mid² < X (rounded down square root).

Code Implementation

• Ensure proper handling of edge cases (e.g., X = 0).
• Demonstrated efficiency and correctness of the solution.

Conclusion

• Efficient square root calculation using binary search.
• Encouragement to like and subscribe for more coding resources.
• Mention of neco.io for coding interview preparation resources.