Valid Perfect Square - Practice Coding Problems

Valid Perfect Square - Problem

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.

Input & Output

Example 1 — Perfect Square

$ Input: num = 16

› Output: true

💡 Note: 16 is a perfect square because 4 * 4 = 16

Example 2 — Not Perfect Square

$ Input: num = 14

› Output: false

💡 Note: 14 is not a perfect square. √14 ≈ 3.74, which is not an integer

Example 3 — Edge Case

$ Input: num = 1

› Output: true

💡 Note: 1 is a perfect square because 1 * 1 = 1

Constraints

1 ≤ num ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given positive integer num

Process

Find if there exists integer k where k² = num

Output

Return true if perfect square, false otherwise

Key Takeaway

🎯 Key Insight: Use binary search to efficiently find the integer square root in O(log n) time

Asked in

f Facebook 15 in LinkedIn 12

The key insight is to find the integer square root efficiently without using built-in sqrt function. Best approach is binary search with Time: O(log n), Space: O(1), offering the optimal balance of speed and simplicity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(√n)	O(1)	Check every number from 1 to num to see if its square equals num
Newton's Method	O(log log n)	O(1)	Use Newton's iterative method to find square root
Binary Search	O(log n)	O(1)	Use binary search to efficiently find the square root

Brute Force — Algorithm Steps

Start with i = 1
Calculate i * i and compare with num
If equal, return true; if greater, return false
Continue until found or exhausted

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Check

Begin with i=1, check if i²=num

Increment

If not found, try next number

Found/Stop

Return true when found or false when i²>num

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool solution(int num) {
    if (num == 1) {
        return true;
    }
    
    long long i = 1;
    while (i * i <= num) {
        if (i * i == num) {
            return true;
        }
        i++;
    }
    
    return false;
}

int main() {
    int num;
    scanf("%d", &num);
    
    bool result = solution(num);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n)

Loop runs from 1 to √n to find the square root

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler