Valid Perfect Square
Given a positive integer num, write a function that 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 Binary Search Approach - O(log n) public boolean isPerfectSquare( int num) { long left = 1 ; long right = num; while (left<= right) { long mid = left + (right -left) / 2 ; if (mid * mid == num) return true ; if (mid * mid < num) { left = mid + 1 ; } else right = mid - 1 ; } return false ; } Square Root Approach - O(sqrt(n)) We have observed the equation and find some similarities, let's discuss with an example. Input: 16 1 + 3 + 5 + 7 = 16 So 1 + 3 + 5 + 7 + 9 + 11 + ... + (2n -1) = (2(n-1) + 1) n/2 = n*n public boolean isPerfectSquare( int num) { int i = 1 ; while (num > 0 ) { num -= i; i += 2 ; } return num == 0 ; }