Java 4ms Runtime Solution


  • 1
    S

    A few tricks here:

    1. Count down from high roots to small roots using Math.sqrt(int) as a starting point.

    2. Check if the root is evenly divisible with the left over of the number, if so do integer division.

    3. Check if we can do better than the best answer already found before recursing.

      public class Solution {

           public int squares(int n, int root,int count,int sqmin) {
      
           if (count>=sqmin) {
               return sqmin;
           }
           int min=0;
           for(;root>0;root--) {
               int sqr=(root*root);
               if (n < sqr) { 
                   continue;
               }
               else if (n%sqr==0) { 
                   min= count+ ((n/sqr)-1);
               } else {
                   min= squares(n-sqr,root,count+1,sqmin);
               }
               if (min < sqmin) {
                   sqmin=min;
               }
           }
           return sqmin;
       }
       public int numSquares(int n) {
           if (n < 1) return 0;
           return squares(n,(int)Math.sqrt(n),1,Integer.MAX_VALUE);
       }
      

      }


  • 0
    G

    if (count>=sqmin) {
    return sqmin;
    }

    I understand all, but the code above. Could you explain these codes in your algorithm?


  • 0
    S

    That is to stop the recursion if any solution found by recursing more would be worse than or equal to the best solution that we already have.


  • 0
    J

    public int numSquares(int n) {
    if (n < 1) return 0;
    return squares(n,(int)Math.sqrt(n),1,Integer.MAX_VALUE);
    ......

    The last input of squares() should be n, because any value n can be divided into n*1.


Log in to reply
 

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