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


  • 0
    K

    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;
        }
    }

  • 0
    C

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


Log in to reply
 

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