#LeetCode: Valid Perfect Square

Also Check: Solutions Of May LeetCoding Challenge (2020)

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:
Input: 16
Output: true

Example 2:
Input: 14
Output: false
Algorithm:

FYI, Square root of any number ends with either 0, 1, 4, 9, 6, or 5.
#If the last digit of any any number is 0, then the last digit of its square root will be 0.
#If the last digit of any any number is 1 or 9, then the last digit of its square root will be 1.
#If the last digit of any any number is 2 or 8, then the last digit #of its square root will be 4.
#If the last digit of any any number is 3 or 7, then the last digit #of its square root will be 9.
#If the last digit of any any number is 4 or 6, then the last digit of its square root will be 6.
#If the last digit of any any number is 5, then the last digit of its square root will be 5.

1). We will follow binary search to resolve this problem.
2). First we will check of the last digit of input is ending with 0, 1, 4, 9, 6, or 5 return false.
3). We will create 4 variables left, right, mid and sq. Left will be initialized with 1 and right with the input number.
4). In every iteration we will find the mid, and then check if the square of mid is equal, less, or greater than the input number.
5). If square of mid is equal to the input number,we will return true.
6). If square of mid is greater than input number, then the square root of the input number will be always less than mid. In this case we will find the number from left to mid-1.
7). If square of mid is less than input number, then the square root of the input number will be always greater than mid. In this case we will find the number from right to mid+1.

GIT URL: Java Solution of Leet Code's Valid Perfect Square problem

Java Solution

ALSO CHECK: Other LeetCode Solutions in Java

-K Himaanshu Shuklaa..