Valid Perfect Square Problem


Description

LeetCode Problem 367. Given a positive integer num, write a function which returns True if num is a perfect square, else False. Do not use any built-in library function such as sqrt.

Example:

1
2
3
4
5
Input: num = 16
Output: true

Input: num = 14
Output: false


Solution

This problem is similar to the Sqrt(x) Problem.

Binary Search Approach

A simple brute force approach is to enumerate all possible solutions from 1 to num/2, and check if there is an integer whose square equals num. If so, return true; otherwise, return false. The time complexity of this approach is O(n).

We can use binary search to speed up the search. We set two pointers l and r. The left pointer l starts from 0, and the right pointer r starts from num. During each iteration, we calculate m to be the average of l and r (m = (l + r) / 2). If m * m equals num, num is a perfect square. We can stop the search and return true. If m * m is larger than x, it means the right range r is too big. We can set r to be m - 1 and keep on searching. If m * m is smaller than num, it means the left range l is too small. We can set l to be m + 1 and keep on searching. We abort the search until l is greater than r.

When l is greater than r, it means we could not find an integer whose square is num. Thus, num is not a perfect square. We return false.

The time complexity of the binary search approach is O(logn), and the space complexity is O(1).


Sample C++ Code

This is a C++ implementation of the binary search approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>

using namespace std;

bool isPerfectSquare(int num) {
    long long l, m, r;
    l = 0, r = num;
    while (l <= r) {
        m = (l + r) / 2;
        if (m*m == num)
            return true;
        if (m*m < num)
            l = m + 1;
        else
            r = m - 1;
    }
    return false;
}

int main() {
    cout << isPerfectSquare(45) << endl;
}




Related Posts

Median of Two Sorted Arrays Problem

LeetCode 4. Given two sorted arrays nums1 and nums2 of...

Valid Perfect Square Problem

LeetCode 367. Given a positive integer num, write a function...

Sqrt(x) Problem

LeetCode 69. Given a non-negative integer x, compute and return...

Search Insert Position Problem

LeetCode 35. Given a sorted array of distinct integers and...