Getting Time Limit Exceed in Java. Can someone help ?


  • 0
    A

    Can someone please explain why I'm getting Time Limit Exceeded with the following code ?

    It's a standard Dynamic Programming approach so I'm not sure what's the problem.

    My approach is to to iterate over how many times I want to use a specific square number, and then recurse for the remaining amount for lower square numbers.

    public class Solution {

    public int numSquares(int n) {
        if(n == 0) {
            return 0;
        } else {
            
            Double x = Math.sqrt(n);
            
            int[] powers = new int[x.intValue()];
            
            int[][] dpt = new int[n][x.intValue()];
            
            for(int j=0; j<x.intValue(); j++) {
                powers[j] = ((Double)Math.pow(j+1, 2)).intValue();
            }
    
            recurse(n, dpt, powers, x.intValue()-1);
            return dpt[n-1][x.intValue()-1];
        }
    }
    
    public void recurse(int n, int[][] dpt, int[] powers, int powerIndex) {
        
        if(powers[powerIndex] == 1) {
            //Base case:
            dpt[n-1][powerIndex] = n;
            
        } else {
            int powerMultiple = n / powers[powerIndex];
        
            int minTotalCount = Integer.MAX_VALUE;
            int tmpTotalCount;
            
            for(int i=0; i<=powerMultiple; i++) {
                tmpTotalCount = i;
                int remaining = n - (i*powers[powerIndex]);
                if(remaining > 0) {
                    if(dpt[remaining - 1][powerIndex-1] == 0) {
                        recurse(remaining, dpt, powers, powerIndex-1);
                    }
                    
                    tmpTotalCount += dpt[remaining - 1][powerIndex-1];
                }
                
                if(tmpTotalCount < minTotalCount) {
                    minTotalCount = tmpTotalCount;
                }
            }
            
            dpt[n-1][powerIndex] = minTotalCount;
            
        }
        
    }
    

    }


Log in to reply
 

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