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

Search in Rotated Sorted Array II Problem

LeetCode 81. There is an integer array nums sorted in...

Search A 2D Matrix Problem

LeetCode 74. Write an efficient algorithm that searches for a...

Find First and Last Position of Element in Sorted Array Problem

LeetCode 34. Given the array nums after the possible rotation...

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...