# Short Python solution using BFS

• ``````def numSquares(self, n):
if n < 2:
return n
lst = []
i = 1
while i * i <= n:
lst.append( i * i )
i += 1
cnt = 0
toCheck = {n}
while toCheck:
cnt += 1
temp = set()
for x in toCheck:
for y in lst:
if x == y:
return cnt
if x < y:
break
toCheck = temp

return cnt
``````

The basic idea of this solution is a BSF search for shortest path, take 12 as an example, as shown below, the shortest path is 12-8-4-0:

• i am impressed by how well the coder understands python..
For example, if swapping x<y with x-y < 0, then the time limit will exceed, because that extra x-y.
Even though in terms of O running time it doesn't add more.
Good job!

• insert below 2 lines will greatly boost the performance: from 1800ms to 400ms

``````                        if x==y:
return cnt
``````

before `temp.add(x-y)`

• You're right, 'while 0 not in toCheck' is actually very slow, thank you for reminding me :)

• That's true! Thanks so much!

• If "if x==y: return cnt" is added and change "while 0 not in toCheck:" to "while True", it also works. But the run time is nearly not changed. Do you know why? Can it be concluded that the "not in set" is as fast as logical judgement?

• @chris.zhang.336 and @Jason1108 , I think this has nothing to do with the speed of "not in set", the whole point is to return as soon as you get the result, and there will be no point of continue to calculate (which consumes much meaningless time)

by the way, I tried change `while 0 not in toCheck:` to `while True` and also get 416ms AC.

• Nice solution! But I am confused about the time complexity of this solution. Is it O(n)?

• It's a little bit hard to say, assume x is the size of lst, I think the time complexity should be O(lg(x)), but I am not 100% sure, correct me if I am wrong :)

• I think it's hard to say in this solution. But the upper bound of the time complexity is O(n).

• My java version of the above logic, but it consistently throws me TLE and failed by 7168 test case, does any one know why?

``````public static int numSquares_20160703(int n) {
if(n < 4) return n;
int rootN = (int) Math.sqrt(n);
int[] squares = new int[rootN];
int a = 1;
while(a*a <= n){
squares[a-1] = a*a;
a++;
}

int result = 0;
q.offer(n);
while(!q.isEmpty()){
int size = q.size();
result++;
for(int i = 0; i < size; i++){
int val = q.poll();
for(int j = 0; j < rootN; j++){
if(val < squares[j]) break;
int newVal = val - squares[j];
if(newVal == 0) return result;
if(newVal > 0) q.offer(newVal);
}
}
}
return result;
}``````

• Thanks for sharing, That is a very clever solution

• @chris.zhang.336

1. What is the complexity of this algorithm? O(n)
2. This fails when you enter n = 4. It should return 1 but instead it returns 4 which is a wrong answer.

• I got same idea in my java solution but I can not tell the space complexity, can someone analyze it?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.