Java beat 78%


  • 0
    B

    Same as most of solutions here start from 2 to sqrt. recursive call on the elements. The trick is not to end up generating duplicate list. To do that only call recursive on the element when its >= square of previous element on the list. also pass in the lower bound for the loop.

        public List<List<Integer>> getFactors(int n) {
            
            List<List<Integer>> ret = helper(n, 2);
            
            return ret;
            
            
        }
        
        public List<List<Integer>> helper(int n, int prev) {
            
            List<List<Integer>> ret = new ArrayList<>();
            
            int sqrt = (int)Math.sqrt(n);
            
            for (int i = prev; i <= sqrt; i++){
                int temp = n/i;
                if (n%i == 0){
                    
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(temp);
                    ret.add(list);
                    
                    if (temp >= i*i){
                        List<List<Integer>> tempRet = helper(temp, i);
                        for (List<Integer> l : tempRet){
                            list = new ArrayList<>();
                            list.add(i);
                            list.addAll(l);
                            ret.add(list);
                        }
                        
                    }
                }
    
            }
            
            return ret;
            
            
        }   
    

Log in to reply
 

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