710. Fewest Squares
A tiler has an unlimited stock of square tiles whose side lengths are whole numbers: 1 by 1, 2 by 2, 3 by 3 and so on. A floor has total area exactly n, and the tiler wants to cover it completely by choosing square tiles whose areas add up to n, repeating sizes as often as needed. The shape of the layout does not matter, only that the tile areas sum to n.
Return the smallest number of square tiles needed. Since a 1 by 1 tile always exists, an answer is always available.
Aim for time O(n * sqrt(n)) and extra space O(n).
Example 1
- Input:
- n = 58
- Output:
- 2
- Explanation:
58 = 49 + 9, which uses two tiles; 58 is not itself a perfect square.
Example 2
- Input:
- n = 83
- Output:
- 3
- Explanation:
83 = 49 + 25 + 9 uses three tiles, and no two squares add up to 83.
Constraints
1 ≤ n ≤ 104
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(n * sqrt(n))
- Space
- O(n)