367.Valid Perfect Square

Posted on | In

Solution 1: accepted 0ms

Binary. Conversion needed to gain precious result. For instance, for number 5, mid will be 2, int 5/2 = 2, which is not what we expect.
Time: O(logn)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isPerfectSquare(int num) {
    if (num == 0) 
        return false;
    int lo = 0;
    int hi = num;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if ((double)mid == num / (double)mid) {
            return true;
        } else if ((double)mid < num / (double)mid){
            lo = mid;
        } else {
            hi = mid;
        }
    }
    if (lo * lo == num || hi * hi == num)
        return true;
    return false;
}