Last active
May 24, 2020 05:54
-
-
Save mukitul/857d2d1027d3ba812876c9ef81fc8727 to your computer and use it in GitHub Desktop.
This approach can check perfect square for any positive integer in optimal time i.e, O(log n)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// this method will return 1 if N is valid perfect square number otherwise -1 | |
public static int validPerfectSquare(long N) { | |
if (N == 1) return 1; | |
long lowPointer = 2, highPointer = N / 2; | |
while (lowPointer <= highPointer) { | |
long mid = lowPointer + (highPointer - lowPointer) / 2; | |
if (mid * mid == N) return 1; | |
else if (mid * mid > N) highPointer = mid - 1; | |
else lowPointer = mid + 1; | |
} | |
return -1; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment