Is It a Square Tiling?
EasyBinary Search
Problem
A tiler has tiles identical square tiles and wants to lay all of them as one perfect square, with the same number of tiles on each side and none left over.
Return true if that is possible (that is, tiles is a perfect square) and false otherwise. Do not use a built-in square root.
Example 1
- Input:
- tiles = 49
- Output:
- true
A 7 × 7 square.
Example 2
- Input:
- tiles = 50
- Output:
- false
7 × 7 leaves one tile over, and 8 × 8 needs 64.
Constraints
- 1 ≤ tiles ≤ 2^31 - 1
Hint
Show the first hint
If a side length s exists, s is between 1 and tiles. How do you compare a candidate s with tiles?
Walkthrough
How to approach it
01Clarify before coding
- Can tiles be 0? No, at least 1 (and 1 is a 1 × 1 square).
- Are floating-point square roots allowed? No, the point is to do it with integers.
- Overflow? s² can reach 4.6 · 10^18 if s goes up to tiles; cap the range or use 64-bit math.
02Brute force
Try s = 1, 2, 3, ... while s² ≤ tiles and check for equality.
Cost: O(√tiles): about 46,000 steps at the top of the range.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.