[LeetCode] 2 Keys Keyboard

Problem: There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:

• Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
• Paste: You can paste the characters which are copied last time.

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

Example:

Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Input: n = 1
Output: 0

Approach: We are going to use bottom-up DP here. We can define a 1D array where table[i] tells the minimum number of steps required to display i A's. Obviously table[n] will be our answer.

Now the main logic here is to get the relations between table[i] and table[i-1]...table[1], right?  Let's understand it; let's say we had j A's on the screen where 1 <= j < i. Now we can say we can copy these j A's and paste it exactly (i - j) / j times to display i A's so total number of operations will be:

f(i) = f(j) + 1 + (i - j) / j

Why? Let's see:

• f(j) - Number of steps to display j A's
• 1 - Copy All
• (i - j) / j - Number of pastes.

Now let's simplify this equation:

f(i) = f(j) + 1 + (i - j) / j

=> f(i) = f(j) + 1 + (i/j) - (j/j)

=> f(i) = f(j) + 1 + (i/j) - 1

=> f(i) = f(j) + i / j

So here is our final relation:

f(i) = f(j) + i / j

We also need to make sure that i should be divisible by j as it's kind of repeated pastes. Now we just need to get the minimum of all such j's where 1 <= j < i and i is divisible by j.

That's all!

Implementation in C#:

    public int MinSteps(int n)

    {

        if (n <= 1)

        {

            return 0;

        }

        int[] table = new int[n + 1];

        for (int i = 2; i <= n; ++i)

        {

            table[i] = int.MaxValue;

            for (int j = 1; j <= i / 2; ++j)

            {

                if (i % j != 0)

                {

                    continue;

                }

                table[i] = Math.Min(table[i], table[j] + i / j);

            }

        }

        return table[n];

    }

Complexity: O(n^2)