# Sharing my Java solution (beats 96.32% of submissions in Java)

• 14 ms, beats 96.32% of submissions in Java.

``````public class Solution {
public int fast_sqrt(int n){
if(n<1) return 0;
if(n<4) return 1;
int prev = (n+1)>>1, curr = ((n+1)>>2)+1;
while(prev > curr){
prev = curr;
curr = (curr*curr+n)/(curr<<1);
}
return prev;
}
public int numSquares(int n) {
if(n==0) return 0;
int sqrt = fast_sqrt(n);
int[] squares = new int[sqrt];
for(int i=0;i<sqrt;i++){
squares[i] = i*i + (i<<1) + 1;
if(n==squares[i]){
return 1;
}
}
int[] two = new int[(n+sqrt)>>1];
int pointer = 0,temp;
for(int i=0;i<sqrt;i++){
for(int j=i;j<sqrt;j++){
temp = squares[i]+squares[j];
if(n == temp){
return 2;
}
two[pointer++] = temp;
}
}
int length = two.length;
for(int i=0;i<sqrt;i++){
for(int j=0;j<length;j++){
if(n == squares[i]+two[j]){
return 3;
}
}
}
return 4;
}
}``````

• bad case: 2932430 output is 4. It should be 3.

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