Leetcode: Factor Combinations

By | 2018 年 9 月 22 日

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

You may assume that n is always positive.
Factors should be greater than 1 and less than n.

Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]
Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]
Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Analyze

Recursively get the factors of n by checking the numbers in range from 2 to n/2. If the number is a factor of n, then recursively get the factors list of the counterpart.

Use a map from integer to factors list to speedup the process.

Time Complexity

The time complexity should be O(n), because in worst case if n = 2^k, there are at most log(n) factors.

For the testing from 2 to n/2, we have O(n) time.
And because this process will also take place in it’s factors, each factor e.g. m will have O(m) time to do this.
But, considering: in condition a >= 2, b >= 2, we have a + b <= a * b, and this conclusion can extends to more than 2 numbers. So the sum of the testing time in factors will still be O(n).
So combine the testing times together, we have O(n) time complexity.

For the recursive method calls, because we have most log(n) factors, so the getFactories will get calculated at most log(n) times.

Thus, combine them all together, we got O(n) time complexity.

Prove of a + b <= a * b

The conditions: a >= 2, b >= 2.

Let's suppose that a <= b
Because a <= b, so we have a + b <= 2b
Because a >= 2, so we have 2b <= ab

Thus: a + b <= 2b <= ab in the condition both numbers are >= 2

Solutions

Ruby

# @param {Integer} n
# @return {Integer[][]}
def get_factors(n)
    @saved_factors ||= {}
    return @saved_factors[n] unless @saved_factors[n].nil?

    factors = []
    2.upto(n/2) do |i|
        if n % i == 0
            j = n / i
            factors << [i, j] if i <= j
            factors_j = get_factors(j)
            factors += factors_j.select{|fj| fj.first >= i}.map{|fj| [i] + fj}
        end
    end

    @saved_factors[n] = factors
end

Beats 100% ruby solutions with cache:

Java

class Solution {
    private Map<Integer, List<List<Integer>>> cache;

    public Solution() {
        this.cache = new HashMap<Integer, List<List<Integer>>>();
    }

    private List<Integer> pair(int i, int j) {
        List<Integer> list = new ArrayList<Integer>(2);
        list.add(i);
        list.add(j);
        return list;
    }

    private List<Integer> extendFactor(int i, List<Integer> sourceFactors) {
        List<Integer> list = new ArrayList<Integer>(sourceFactors.size() + 1);
        list.add(i);
        for(Integer j : sourceFactors) {
            list.add(j);
        }
        return list;
    }

    public List<List<Integer>> getFactors(int n) {
        // System.out.println("get:" + n);
        if(this.cache.containsKey(n)) {
            return this.cache.get(n);
        }

        List<List<Integer>> factors = new ArrayList<List<Integer>>();
        for(int i = 2; i <= n / 2; ++i) {
            if(n % i != 0) {
                continue;
            }
            // System.out.println(i);
            int j = n / i;
            if(i <= j) {
                factors.add(pair(i, j));
            }
            List<List<Integer>> factorsForJ = getFactors(j);
            for(List<Integer> factorJ : factorsForJ) {
                if(factorJ.get(0) >= i) {
                    factors.add(extendFactor(i, factorJ));
                }
            }
        }

        this.cache.put(n, factors);
        return factors;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注