Skip to content

Instantly share code, notes, and snippets.

@mukitul
Last active May 24, 2020 05:54
Show Gist options
  • Save mukitul/857d2d1027d3ba812876c9ef81fc8727 to your computer and use it in GitHub Desktop.
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 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