367. Valid Perfect Square - cocoder39/coco39_LC GitHub Wiki

367. Valid Perfect Square

corner case:

• check overflow mid <= INT_MAX /mid
• check divider == 0

O(lg num)

bool isPerfectSquare(int num) {
        int start = 0, end = num;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(mid <= INT_MAX /mid && mid * mid == num) {
                return true;
            }
            if (mid < num / mid) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        
        if ((start != 0 && start <= INT_MAX / start && start * start == num) || (end != 0 && end <= INT_MAX / end && end * end == num)) { 
            return true;
        }
        return false;
    }

use start == num / start can only tell start * start <= num instead of start * start == num. However start * start may cause overflow. we can use start == num / start && num % start == 0

bool isPerfectSquare(int num) {
        int start = 1, end = num; //[start, end]
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (mid < num / mid) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        return (start == num / start && num % start == 0) ||
               (end == num / end && num % end == 0);
    }

second round

bool isPerfectSquare(int num) {
        int start = 1, end = num;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (mid <= INT_MAX / mid && mid * mid == num) {
                return true;
            } else if (mid <= num / mid) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return (start <= INT_MAX / start && start * start == num) || (end <= INT_MAX / end && end * end == num);
    }