Share a bit the thought process - short Java 3 ms (Bottom up) and (Top Down)


  • 2
    C
    1. Let's consider how to find a list of candidates that forms n1*n2=n, let's call [n1,n2] a 2-tuple, we loop from 2 to sqrt(n) and find all n1 that is a factor of n, then n2=n/n1. n1<n2 always.

    2. how to build our solution that from above sub-problem? Essentially you ask all the N-tuples that can multiply to n. and N-tuple is made up by N-1-tuple plus one number. Above described process is clearly a recursion, and the termination condition is you've tried all combinations.

    3. But what forms the combination? suppose a number n%i==0, a full set would be

    • 2-tuple, [i, n/i]
    • N-tuple (N>2) eg. [i, all N-tuples of (n/i)]

    So below is the bottom up approach

    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;
    }
    

    And top down using stack.

    public List<List<Integer>> getFactors(int n) {
    
            List<List<Integer>> res = new ArrayList<>();
            combination(n, 2, new Stack<>(), res);
            return res;
        }
    
        public void combination(int n, int start, Stack<Integer> stack, List<List<Integer>> res) {
    
            int end = (int) Math.sqrt(n);
            for (int i = start; i <= end; i++) {
                if (n % i != 0) continue;
                res.add(new ArrayList<>(stack));
                res.get(res.size() - 1).add(i);
                res.get(res.size() - 1).add(n / i);
    
                stack.push(i);
                combination(n / i, i, stack, res);
                stack.pop();
            }
        }

Log in to reply
 

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