3ms Divide & Conquer JAVA solution


  • 0
    S
    private HashMap<Integer, List<List<Integer>>> map = new HashMap<>();
    
    public List<List<Integer>> getFactors(int n) {
        if (map.containsKey(n)) {
            return map.get(n);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int f = 2; f * f <= n; f++) {   //factor will not include 1 and n itself
            if (n % f == 0) {
                List<Integer> list = new ArrayList<>();
                list.add(f);
                List<List<Integer>> nextAns = getFactors(n / f);  //divide into small problems
                for (List<Integer> eachNext : nextAns) { 
                    if (eachNext.get(0) >= f) {
                        List<Integer> newList = new ArrayList<>(list);
                        newList.addAll(eachNext);
                        ans.add(newList);
                    }
                }
                if (n / f >= f) {  //don't forget n/f itself 
                    list.add(n / f);
                    ans.add(list);
                }
               
            }
        }
        map.put(n, ans);  //1 and prime numbers will have empty ans list
        return ans;
    }

Log in to reply
 

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