383. Perfect Square Test
A mosaic maker has n identical stones and wants to know whether they can be laid out as a full square grid, with the same whole number of stones along each side and none left over.
Return true if there is a whole number k with k * k == n, and false otherwise. Do not use any built-in square-root or power function and avoid floating-point arithmetic. Your solution should take O(log n) time. Be careful: k * k can overflow a 32-bit integer when n is large.
Example 1
- Input:
- n = 49
- Output:
- true
- Explanation:
7 * 7 = 49, so the stones form a 7 by 7 square.
Example 2
- Input:
- n = 50
- Output:
- false
- Explanation:
No whole number squared equals 50, so the answer is false.
Constraints
1 ≤ n ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)