Valid Perfect Square
Easy · Binary Search · Math · Binary Search
Problem
Given a positive integer num, return true if num is the square of an integer (num = k · k for some whole number k), and false otherwise.
Do not call a built-in square root or power function. Find the candidate root yourself.
Examples
Input: num = 49 Output: true
7 · 7 = 49.
Input: num = 50 Output: false
7 · 7 = 49 and 8 · 8 = 64, so no whole number squares to 50.
Input: num = 1 Output: true
1 · 1 = 1.
Constraints
- 1 <= num <= 2^31 - 1
Approaches
- Count up from 1 — time O(√num), space O(1)
Follow-up
Newton’s method finds the root faster still: start at x = num and repeat x = (x + num // x) // 2 while x · x > num. It converges in a handful of steps, doubling the correct digits each time, and stays in integers.
Related problems
Start free on Cariara · Coding problems · System design studio
