Solution by colbs255


  • 0
    C

    Approach #1 Brute Force Recursion

    Intuition

    This problem is similar to finding the factors of n. If a number is a factor of
    n, the number can be copied and then pasted repeatedly to obtain n, which is
    essentially multiplication.

    For example, if n is 12 and we are looking at the number 3, 3 is a factor of 12, so you can copy and paste 3 to get 6 As total (2 steps), then paste again to get 9 As total (1 step), then paste one more time to get 12 (1 step) with 4 steps. To get the total number of steps for 12, you have to add 4 to the number of steps needed to obtain 3, which can be solved recursively by calling minSteps(3). Notice that 4 equals 12 / 3. This is because you have to paste 3 times (12 / 3 - 1) plus the copy step for 3.

    Therefore, for a given factor f and a number n, the steps needed can be solved as
    $$
    minSteps(f) + /frac{n}{f}
    $$

    Algorithm

    This algorithm iterates over every positive integer less than n. If the integer is a factor of n, determine the number of steps needed to obtain n with that factor. If the number of steps is less than the minimum number of steps already known, set minSteps equal to the new answer.

    Java

    public class Solution {
        public int minSteps(int n) {
            if (n == 1) return 0;
            int min = Integer.MAX_VALUE;
            for (int factor = 1; factor < n; factor++) {
                if (n % factor == 0) {
                    int stepsForFactor = minSteps(factor) + n / factor;
                    if (stepsForFactor < min) min = stepsForFactor;
                }
            }
            return min;
        }
    }
    

    Complexity Analysis

    • Time Complexity : $$O(n * n!)$$ because it is similar to string permutation problem.

    • Space Complexity: $$O(n * n!)$$


    Approach #2 Dynamic Programming

    Intuition
    In the above solution, we often make function calls with numbers that we have already used before. If we use an array to keep track of the solutions to each subproblem, we can have a constant time lookup.

    Additionally, the min number of steps will always come from copying and pasting the highest amount of characters possible; therefore, each solution will use the largest subproblem possible. Once the largest subproblem is found, no other subproblems have to be looked at.

    Lastly, if there does not exist a factor that is less than or equal to the square root of a number other than 1, then the number is guaranteed to be prime since each factor must have another factor that it can be multiplied by to obtain n. Thus, we only have to look at factors that are less than or equal to the square root of n.

    Algorithm

    This algorithm saves the answer to each subproblem in an array and uses the largest subproblem possible in each solution. It only looks at numbers less than or equal to the square root of n, and if no suitable subproblem other than 1 exists, then the number must be prime, so it will take n steps.

    Java

    class Solution {
        public int minSteps(int n) {
            // store subproblems in table
            int[] table = new int[n + 1];
            table[1] = 0;
            for (int sub = 2; sub <= n; sub++) {
                int previous = 2;
                // default value if prime number
                table[sub] = sub;
                while (previous * previous <= sub) {
                    if (sub % previous == 0) {
                        //suitable factor found
                        table[sub] = table[sub / previous] + previous;
                        break;
                    }
                    previous++;
                }
            }
            return table[n];
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n^2)$$ For every subproblem using the number x, we are doing x iterations at most.
    • Space complexity : $$O(n)$$ We use an n-length table to store the solution to each subproblem.


Log in to reply
 

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