[Alogrithm] Valid Perfect Square

Valid Perfect Square

Problem statement:

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.

This problem can be solved by solving the square root of the given number. So it comes back to the sqrt(x) implementation.

Souliton 1 : Newton-Raphson Method.

The problem can be rewritten as: Given a function f(x) = x^2 - a, find the x so that f(x) = 0. We can use Newton-Raphson Method to approximate the x.

There's a lot of explanation on  that approach. So I won't explain futher. The following links will provide enough details:

http://www.sosmath.com/calculus/diff/der07/der07.html

https://en.wikipedia.org/wiki/Newton%27s_method

Code Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: bool isPerfectSquare(int num) { float x0 = (float)num/2; while (true) { float x1 = x0 - (x0 * x0 - num) / (2.0 * x0); if (fabs(x1 - x0) < 0.0001) break; x0 = x1; } int x = x0; return (x*x == num); } };

Solution 2: Binrary Search:

One can use binary search to find the answer. There problem with binary search is that sometimes we will not hit the correct answer during the binary searching loop. Under that scenario the lhs and rhs value in the end will be a bound for the correct answer.

So for this problem we just need to check the bound to see wether their square equal to the target number.

(I have problems with the approach in the Sqrt(x) problem, I guess we should pick the lower bound for that case)

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: bool isPerfectSquare(int num) { long long lhs = 1; long long rhs = num; while (lhs < rhs) { long long mid = lhs + (rhs - lhs) / 2; long long square = mid * mid; if (square == num) { return true; } else if (square < num) { lhs = mid+1; } else { rhs = mid-1; } } return (lhs * lhs == num || rhs * rhs == num); } };