650. 2 Keys Keyboard

Time: O(n√n)

Space: O(n)

Intuition

The minimum steps to get n 'A's is the sum of prime factors of n. Each prime factor p means: copy current and paste (p-1) more times.

Algorithm

1Factor n into primes.
2Sum of all prime factors (with multiplicity) = minimum operations.

Example Walkthrough

Input: n=6

1.6 = 2×3. Start with 1 A. Copy+Paste once → 2A (2 steps). Copy+Paste twice → 6A (3 steps). Total = 5.

Output: 5

Common Pitfalls

•n=1 → 0 operations (already have 1 A). Each prime factor p costs p operations.

650.cs

// Approach: DP where dp[i] is the min operations to reach i 'A's; for each
// divisor j of i, dp[i] = min(dp[i], dp[i/j] + j).
// Time: O(n√n) Space: O(n)

public class Solution
{
    public int MinSteps(int n)
    {
        int[] dp = new int[1005];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 2;
        dp[3] = 3;

        for (int i = 4; i <= n; i++)
        {
            dp[i] = i;
            for (int j = 2; j < i; j++)
            {
                if (i % j == 0)
                    dp[i] = Math.Min(dp[i], dp[i / j] + j);
            }
        }
        return dp[n];
    }
}

Was this solution helpful?