Recursive Java Solution beats 95.94%


  • 0
    Z
    public class Solution {
    public int minRes;
    public int numSquares(int n) {
        minRes = Integer.MAX_VALUE;
        find(n, 0);
        return minRes;
    }
    
    public void find(int n, int count){
        if(n < 4){
            count += n;
            if(count < minRes){
                minRes = count;
            }
            return;
        }
        int newCount = count + 1;
        if(newCount > minRes){
            return;
        }
        int maxsqrt = (int)Math.sqrt(n);
        if(maxsqrt*maxsqrt == n){
            if(newCount < minRes){
                minRes = newCount;
            }
            return;
        }
        int i = maxsqrt;
        int mid = (maxsqrt + 2)/2;
        while(i>= mid){
            find(n - i*i, newCount);
            i--;
        }
    }
    

    }


  • 0
    R

    It's really fast, but could you explain it with more detail? Especially mid = (maxsqrt + 2)/2


  • 0
    Z

    Because I want to find the median between 2 and the current max square root. 2 is the smallest square root in this case(because 2*2 = 4, and 4 is the smallest element that counts in this question). Hope it helps :)


Log in to reply
 

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