C++, O(sqrt(n)), DP and greedy prime number solution


  • 5
    Z

    We can solve this problem using standard DP or greedy algorithm, based on two observations.

    1. if n%k == 0, we can copy n/k and paste k-1 times, so dp[n] = min (dp[n/k]+k, for all valid k);
    2. if k is not a prime number, k = ab, we can copy n/k and paste a-1 times, then copy n/b and copy b-1 times, the total is dp[n/k]+a+b. Because a+b is always <= ab, by induction the answer is the sum of all prime number factors of n;

    Standard DP memorization solution, 3 ms, O(n*sqrt(n))

    class Solution {
    public:
        int minSteps(int n) {
            if (n == 1) return 0;
            vector<int> dp(n+1, 0);
            dp[2] = 2;
            return helper(dp, n);
        }
    private:
        int helper(vector<int>& dp, int k) {
            if (dp[k]) return dp[k];
            int ans = k;
            for (int i = 2; i <= sqrt(k); i++) {
                if (k%i == 0) {
                    ans = min(ans, helper(dp, i)+k/i);
                    ans = min(ans, helper(dp, k/i)+i);
                } 
            }
            dp[k] = ans;
            return ans;
        }
    };
    

    Greedy, 3 ms, O(sqrt(n))

    class Solution {
    public:
        int minSteps(int n) {
            int ans = 0;
            for (int i = 2; i <= sqrt(n); i++) {
                while (n%i == 0) {
                    ans += i;
                    n /= i;
                }
            }
            if (n > 1) ans += n;
            return ans;
        }
    };
    

  • 1
    M

    Um... I don't think your solution is a DP solution but a recusion solution in fact cause that there is not a iteration operation in your solution.


  • 0
    Z

    @microface The first solution is memoization DP with overlapping subproblems. Try some examples to see, such as n = 16.
    The second is a greedy solution, optimized from DP. I am not smart enough to come out with the second solution directly. The first one is my original solution during the contest.


  • 0
    B

    Amazing greedy algorithm and proof!


Log in to reply
 

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