Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Valid Perfect Square
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

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.

Examples

    • Input: 49
    • Expected Output: true
    • Justification: (7 * 7) equals 49.
    • Input: 55
    • Expected Output: false
    • Justification: There is no integer whose square is 55.
    • Input: 0
    • Expected Output: false
    • Justification: 0 is not considered a perfect square.

Constraints:

  • 1 <= num <= 2<sup>31</sup> - 1

Solution

  • Step 1: Start
    • Start by checking if the number is less than 2.
  • Step 2: Binary Search Approach
    • Implement a binary search between 2 and the number.
    • Calculate the middle and check if its square is equal to the given number.
    • If it is equal, return true.
    • If it’s less, perform a binary search on the right half.
    • If it’s more, perform a binary search on the left half.

Algorithm Walkthrough

Given an input of 49:

  • Start by checking if 49 is less than 2. It is not, so proceed.
  • Implement a binary search between 2 and 49.
    • Calculate the middle number: ((2 + 49) / 2 = 25)
    • (25 * 25) is more than 49, so perform a binary search on the left half (2 to 25).
    • New middle: ((2 + 25) / 2 = 13)
    • (13 * 13) is more than 49, so perform a binary search on the left half (2 to 13).
    • New middle: ((2 + 13) / 2 = 7)
    • (7 * 7) equals 49, return true.
Image

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: The time complexity of this algorithm is (O(log n)) because it employs a binary search strategy, effectively halving the search space in each iteration.

  • Space Complexity: The space complexity is (O(1)), as it uses a constant amount of additional memory space, not dependent on the input size.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible