Is Valid Perfect Square easy or hard?

Valid Perfect Square is classified as an Easy problem on LeetCode with an acceptance rate around 45%. The challenge is recognizing that binary search can be applied to integers even when the input is not an array.

How to solve Valid Perfect Square in O(log n)?

Use binary search on the range from 1 to num. Compute mid * mid and compare it with num to decide whether to move left or right in the search range. If a value squared equals num, it is a perfect square. This halves the search space every step, producing O(log n) time complexity.

What is the best approach for Valid Perfect Square?

Binary Search is the most common approach. It searches the possible integer root range and checks whether mid * mid equals the given number. The method runs in O(log n) time and O(1) space and avoids floating point precision issues. Newton's Iteration is another efficient alternative but appears less frequently in interviews.

What data structure is used in Valid Perfect Square?

No complex data structure is required. The problem relies mainly on mathematical reasoning and the binary search algorithm. A few integer variables track the search boundaries and midpoint.

What is the time complexity of Valid Perfect Square?

The optimal solutions run in O(log n) time. Binary Search halves the search space each iteration while Newton's Method rapidly converges to the square root approximation. Both approaches use constant O(1) extra space.

Valid Perfect Square Python or Java solution approach?

Both Python and Java implementations typically use binary search. The algorithm repeatedly checks mid * mid against the target number while adjusting the search range. Some implementations use num / mid instead of mid * mid to prevent integer overflow in Java.

Is Valid Perfect Square asked at Google, Amazon, or Meta?

This problem appears in interview preparation lists for companies such as Google, Amazon, and Microsoft because it tests binary search reasoning and integer overflow handling. Variants of integer square root and perfect square validation frequently appear in technical screens.

Description Solution Video 8:44

367. Valid Perfect Square

Easy44.8% acceptance8 companies

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Example 1:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2:

Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

Constraints:

1 <= num <= 2³¹ - 1

Asked at 8 companies

HCLTech LinkedIn SAP Microsoft

Google Amazon Meta Bloomberg

Topics

Binary Search Math

8:44

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

367. Valid Perfect Square

Asked at 8 companies

Topics

Similar problems