Problem Statement

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Examples

1. • Input: 49
   • Expected Output: true
   • Justification: (7 * 7) equals 49.
2. • Input: 55
   • Expected Output: false
   • Justification: There is no integer whose square is 55.
3. • Input: 0
   • Expected Output: false
   • Justification: 0 is not considered a perfect square.

Constraints:

• 1 <= num <= 2³¹ - 1

Solution

• Step 1: Start
  • Start by checking if the number is less than 2.
• Step 2: Binary Search Approach
  • Implement a binary search between 2 and the number.
  • Calculate the middle and check if its square is equal to the given number.
  • If it is equal, return true.
  • If it’s less, perform a binary search on the right half.
  • If it’s more, perform a binary search on the left half.

Algorithm Walkthrough

Given an input of 49:

• Start by checking if 49 is less than 2. It is not, so proceed.
• Implement a binary search between 2 and 49.
  • Calculate the middle number: ((2 + 49) / 2 = 25)
  • (25 * 25) is more than 49, so perform a binary search on the left half (2 to 25).
  • New middle: ((2 + 25) / 2 = 13)
  • (13 * 13) is more than 49, so perform a binary search on the left half (2 to 13).
  • New middle: ((2 + 13) / 2 = 7)
  • (7 * 7) equals 49, return true.