Two (2) Keys Keyboard
Lintcode Programming Question 975 (Dynamic Programming)
Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:
Copy All: You can copy all the characters present on the notepad (partial copy is not allowed). Paste: You can paste the characters which are copied last time. Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.
If we think about the answers from first principle, we note that if n = 1, the minimum number of steps permitted would be 0, since ‘A’ is already on the notepad.
If n = 2, we can only get ‘A’ by one copy and one pasting. Hence answer is 2.
If n = 3, this case is non-trivial. At this point, you should realize that there is no way for ‘AAA’, if you have already done the step to get ‘AA’. So if this is a dynamic programming question, when n = 3, it has no recurrence relationship to the last neighbor n = 2. Rather, to get ‘AAA’, you have to copy ‘A’ once, and paste 2 times.
At n = 4, you suddenly realize you have two options to get ‘AAAA’:
- Copy ‘A’ and paste 3 times; or
- Minimum steps operations to get n = 2 i.e. ‘AA’ and copy then paste, i.e. f(4) = f(2) + 1 copy + 1 paste= 4.
Finally, you thought that there is a recurrence relationship.
At n =5, same issue you encountered at 3, you cannot reuse the work of the previous neighbor n = 4, rather you have to copy ‘A’ once and paste 4 times.
From n = 6 to n = 10, see the filled up table. You should be able to fill it up yourself.
At this point, we obviously would want to be able to code so that the computer instead of us can do the grunt work. However, have we found the recipe?
Revelations — Prime Case of Oddity
It seems that whenever the n is odd, that we have to copy ‘A’ and copy n-1 times. That is when n is odd, the minimum number of operations is equal to n itself. Being boys and gals of STEM, we have to prove this, which we obviously cannot test for all cases of n being odd. So we wield our best tool: Proof by Contradiction.
Let n = 11, again, the hypothesis above holds: We copy ‘A’ and paste 10 times!
Let n = 13, again: We copy ‘A’ and paste 12 times.
Let n = 15, again: We copy ‘A’ and paste 14 times….wait…we can do copy ‘AAA’ and paste 4 times. For the latter to get to ‘AAA’, minimum cost is 3 so yielding a minimum operations of 3 + 1 copy + 4 copy = 8 operations! A major contradiction to hypothesis. Something is up!
Whenever, we look at odd numbers, I exhort you to also think of Prime Numbers. We know that 3, 5, 7, 9, 11, 13, 15,… are odd numbers and 2, 3, 5, 7, 9, 13, 17…m are Prime Numbers. Because of the overlaps, whenever we are finding a pattern for odd numbers, we should also check whether there is a pattern for Prime Numbers.
In our case, if we look at n = 2, we realize the way we get the minimum operation is similar to other Prime Numbers. i.e. copy ‘A’ and copy n-1 times.
Hypothesis 1: If n is a Prime Number, copy ‘A’ and copy n-1 times which is n operations as the minimum operations.
Prime Numbers and Composite Numbers
For n = 15, it is a composite number. Any composite number can be decomposed to prime number factors i.e. Prime Factors. Using this perspective, if we look at n = 15, we already concluded above that the minimum number of operations is taking ‘AAA’, copy it and paste 4 times. To get ‘AAA’ it took 3 operations, and the copy and paste is 5 operations. Could we get the answer using previous values of n! Rhetorically YES
Hypothesis 2: If n is a Composite Number (not a prime), decompose to its Prime Factors and for add up the minimum operations for each of the Prime Factors if each are n.
To know whether a number is a Prime Number and also to get Prime Factors for Composite Numbers, see this Post.
On to our code in Python (the best language now).
@param n: The number of 'A'
@return: the minimum number of steps to get n 'A'
def minSteps(self, n):
if n == 0 or n == 1:
primeTable = self.findPrimeNumbersToN(n)
res = 0
if primeTable[n] == False: #is not prime
#do prime factorisation
primeFactors = self.getListOfPrimeFactorsForComposite(n, primeTable)
for primeFactor in primeFactors:
res += primeFactor
res = n #n is a prime number, return value of itself
Happy coding. If this helped you, please clap.