```
int numSquares(int n)
{
deque<int> remain;
remain.push_back(n);
for (int i = 1, count = 1, nextCount = 0; i < n; ++i, swap(count, nextCount))
{
for (; count != 0; --count, remain.pop_front())
{
int maxRoot = sqrt(remain.front());
if (maxRoot * maxRoot == remain.front()) { return i; }
for (int endRoot = sqrt(remain.front() / 3); maxRoot >= endRoot; --maxRoot)
{
remain.push_back(remain.front() - maxRoot * maxRoot);
++nextCount;
}
}
}
return n;
}
```

for example:

if n = 111

while i = 1

deque[111]

and maxRoot == 10

if (maxRoot^2 == deque.front()) return i

else

deque[111 - 10*10][111 - 9*9][111 - 8*8][111 - 7*7][111 - 6*6]

endRoot is 6 (because 5,4,3,2,1 is unnecessary to check, so i cut these)