367. Valid Perfect Square

UnknownView on LeetCode

Math Binary Search

Time: O(log n)

Space: O(1)

Intuition

Binary search for an integer x such that x^2 == num. Use long to avoid overflow.

Algorithm

1lo=1, hi=num.
2While lo <= hi: mid = lo + (hi-lo)/2. sq = (long)mid*mid.
3If sq == num: return true. If sq < num: lo=mid+1. Else: hi=mid-1.
4Return false.

Example Walkthrough

Input: num = 16

1.mid=8: 64>16 -> hi=7. mid=4: 16==16 -> true.

Output: true

Common Pitfalls

•Use long for sq - mid*mid overflows int for large num.

367.cs

// Approach: Binary search for an integer r in [1, num] such that r*r == num.
// Time: O(log n) Space: O(1)

public class Solution
{
    public bool IsPerfectSquare(int num)
    {
        int l = 1;
        int r = num;

        while (l < r)
        {
            int m = (l + r) / 2;
            if (m >= num / m)
                r = m;
            else
                l = m + 1;
        }

        return l * l == num;
    }
}

Was this solution helpful?