Recursive DFS Solution in Java which I believe has O(n) run-time


  • 1
    A

    public class Solution {

    public int numSquares(int n) {
        return dfs(n,0,n);
    }
    
    public int dfs(int n, int level, int min) {
        if(n == 0 || level >= min) return level;
        for(int i = (int) Math.sqrt(n); i > 0; i--) {
            min = dfs(n - ((int)Math.pow(i,2)), level+1, min);
        }
        return min;
    }
    

    }

    I'm not certain on my math so please correct me if I'm wrong, but the run-time should be O(n^(1/2) * n^(1/4) * n^(1/8) * ...), repeating as many times as there are layers in the minimum, which regardless of the number of layers approaches O(n).


  • 0
    T

    ((int)Math.pow(i,2)) is an awful waste to say i*i ;)


  • 0
    T

    I'd like to see a detailed runtime analysis for this if anyone knows one, as it highly depends on what's the most trivial perfect square sum for the input (first DFS result where n==0): a*biggest_square + b*smaller_square + c*other_smaller_square ..., for example for 48=36+9+1+1+1. Here're the number of dfs calls for a few inputs:

    n		dfs		dfs-for
    48		208		59
    49		8		1
    100		11		1
    200		159		15
    300		3011	324
    400		21		1
    500		396		23
    600		7755	532
    1000	1174	149
    2000	1574	45
    5000	3927	71
    10000	101		1
    100000	78550	317
    

    dfs column is the number of entries
    dfs-for column is the number of calls that don't get cut off by the guard

    When I say highly depends I mean highly: 10000000 runs in 22ms, but 99999 is TLE. The verifier fails to finish for some numbers that this algorithm handles with ease and vice versa.


Log in to reply
 

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