Super Simple Recursion + DP (caching) 3ms solution. Interview friendly!


  • 0
    F

    The basic approach is to recursively factor a number. That is, for a given number, start by finding its divisors smallest to largest. For each divisor, check if you already have a cached factorization. If not, call the function recursively to get its factorization. Probably the only tricky part is ensuring there's no dupes. We can guarantee that by finding the divisors in increasing order so that factorizations are also in increasing order. That way, we can ignore factorizations for the quotient that start at a number smaller than our divisor.

    class Solution {
        unordered_map<int,vector<vector<int>>> factors;
    public:
        vector<vector<int>> getFactors_r(int n, bool in_call)
        {
            vector<vector<int>> result;
            if (in_call)
            {
                if (factors.count(n)) return factors[n]; //already memoized
                result.push_back({n});
            }
            for (int i=2; i*i<=n; ++i){ //start at 2 b/c 0 and 1 are special cases we skip
                int r = n % i; //remainder
                if (!(n%i)){ //n divisible by i
                    int q = n/i; //quotient
                    //get factors of quotient
                    if (!factors.count(q))
                        factors[q] = getFactors_r(q,true);
                    const auto& q_fact = factors[q];
                    for (auto f : q_fact){
                        if (i <= f[0]){ // if we don't have this, we'll get dupes.
                            f.insert(f.begin(),i);
                            result.push_back(f);
                        }
                    }
                }
            }
            return result;
        }
        
        vector<vector<int>> getFactors(int n) {
            return getFactors_r(n,false);
        }
    };
    

Log in to reply
 

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