Why is this solution so slow and how to make is faster?


  • 0
    E

    The idea is to recursively choose the least possible factor and add it into the list, while at the same time update n. Currently, it is over 300ms! I tried to mimic other solutions by changing i*i<=n but it does not work.

    Can someone take a look?

    public List<List<Integer>> getFactors(int n) {
    	List<List<Integer>> list =  getFactors(n, n, 2);
    	if(list.isEmpty() || list.get(0).isEmpty()) return new LinkedList<List<Integer>>();
    	return list;
    }
    
    private List<List<Integer>> getFactors(int n, int rem, int min) {
    	List<List<Integer>> list = new LinkedList<List<Integer>>();
    	if(rem<=1) {
    		list.add(new LinkedList<Integer>());
    		return list;
    	}
    	for(int i=min; i<=rem && i<=n/min; i++) {
    		if(rem%i==0) {
    			List<List<Integer>> prev = getFactors(n, rem/i, i);
    			for(List<Integer> inner : prev) {
    				LinkedList<Integer> head = new LinkedList<Integer>(inner);
    				head.addFirst(i);
    				list.add(head);
    			}
    		}
    	}
    	return list;
    }
    

  • 0
    P
    This post is deleted!

  • 0
    C

    Q: Why is it so slow?
    A: upper bound of for loop is sqrt(n), not n/min

    Q: when you use sqrt(n) why it doesn't work?
    A: in for loop you are asking the function to return N-tuples that multiplies to be n, but most people miss the 2-tuple made up by [i,i/n]

    Below is the the code using your API, I pruned the parameters a bit also, it's 4ms, when you get rid of Arrays.asList it's 2-3 ms.

    public List<List<Integer>> getFactors(int n) {
        return getFactors(n, 2);
    }
    
    private List<List<Integer>> getFactors(int n, int min) {
        List<List<Integer>> list = new LinkedList<>();
    
        int end = (int) Math.sqrt(n);
        for (int i = min; i <= end; i++) {
            if (n % i != 0) continue;
            list.add(new LinkedList<>(Arrays.asList(i, n/i)));//add 2-tuple
    
            List<List<Integer>> prev = getFactors(n / i, i);
            for (List<Integer> inner : prev) ((LinkedList<Integer>) inner).addFirst(i);
            list.addAll(prev);//add N-tuple(N>2)
        }
    
        return list;
    }
    

Log in to reply
 

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