1.Introduction
I regularly practice leetcode if not always on a daily basis. The reasons that I do this are: to keep my coding skills sharp, to deepen my understanding of algorithms and data structures and to prepare for coding challenges and technical interviews. Recently, I solved Leetcode's #650-the 2 keys keyboard using dynamic programming and I have decided to share my approach to solving this problem.Below is a description of the problem.
- 2 Keys Keyboard
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 1:
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'.
Example 2:
Input: n = 1
Output: 0
Constraints:
1 <= n <= 1000
2.First Thoughts
I read the problem and the topics it was listed under. It was listed as Math and Dynamic Programming. My understanding was that there were 2 types of operations: a copy and paste and a paste. I was at first baffled and confused about where to start. I mean how could I minimize the number of operations to achieve this task? The fact that it was listed as dynamic programming gave me an idea-use a 1-d array to store the results of subproblems but I was still baffled.
3.Attempts & Failures
I read the hints. Only 1 was provided. It said "How many characters may be there in the clipboard at the last step if n = 3? n = 7? n = 10? n = 24?". This confused me more. I decided to try something. I could not come up with anything so I decided to reread the problem. On doing so, I realized my first error. 2 types of operations were allowed: a copy all and a paste.This helped. I did some thinking and realized that for a final string of 6,I could do a copy and paste of 3 characters and ditto for a string of 4 characters. It was progress but unfortunately not enough. I decided to read the discussion.
2 observations.
If n is a prime=> ans=n
If n=2^k=> ans=2*k
Something to do with prime factorization, maybe Sieve method can play again, not very necessary.
Have a nice day.
This was helpful but still I struggled.
4. The Breakthrough
I decided to give it a rest and to come back to it later. I was eating lunch and my mind thought about it. I had a realization!!! If the final string was 1000 characters, I could minimize by performing a copy and paste on a string of 500 problems. If it was prime, I could perform a copy and paste of 1 character n times. If it was a string of 27 characters, I could copy a string of 9 characters and paste it twice. So I found a solution. Create a 1-d array of length n+1.Iterate from the index 2 to the end of the array,if the current index is prime, record its number.Otherwise,get its greatest factor,go to that position in the array and calculate the current value by adding the dp value of the highest factor and the quotient of the current value/highest factor.
if(isPrime(i) dp[i]=i;
else dp[i]=dp[highestFactor(i)]+(i/highestFactor(i)).
With this in mind, I attempted a solution. I attempted to do this in Java. Here was my first solution.
class Solution {
public int minSteps(int n) {
int []dp= new int[n+1];
for(int i=2;i<n+1;i++){
if(isPrime(i))dp[i]=i;
else {
//System.out.println
dp[i] =dp[highestDivisor(i)]+(i/highestDivisor(i));
}
}
return dp[n];
}
public int highestDivisor(int n) {
if (n <= 1) return -1; // No proper divisor exists for 0 or 1
for (int i = n / 2; i >= 1; i--) {
if (n % i == 0) {
return i; // First divisor found from the top is the highest
}
}
return -1; // Should never reach here for n > 1
}
public boolean isPrime(int n) {
if (n <= 1) return false; // 0 and 1 are not prime
if (n <= 3) return true; // 2 and 3 are prime
if (n % 2 == 0 || n % 3 == 0) return false; // eliminate multiples of 2 and 3
// Only check up to √n using 6k ± 1 optimization
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
}
As part of my recent decision to try and get solutions in at least 4 languages (Java, c# ,c++ and javascript),I attempted to achieve solutions in c#,c++ and javascript. I first tried c# and the following solution was accepted.
public class Solution {
public int MinSteps(int n) {
int []dp= new int[n+1];
for(int i=2;i<n+1;i++){
if(IsPrime(i))dp[i]=i;
else dp[i] =dp[HighestDivisor(i)]+(i/HighestDivisor(i));
}
return dp[n];
}
public int HighestDivisor(int n) {
if (n <= 1) return -1; // No proper divisor exists for 0 or 1
for (int i = n / 2; i >= 1; i--) {
if (n % i == 0) {
return i; // First divisor found from the top is the highest
}
}
return -1; // Should never reach here for n > 1
}
public bool IsPrime(int n) {
if (n <= 1) return false; // 0 and 1 are not prime
if (n <= 3) return true; // 2 and 3 are prime
if (n % 2 == 0 || n % 3 == 0) return false; // eliminate multiples of 2 and 3
// Only check up to √n using 6k ± 1 optimization
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
}
I then attempted c++ and my solution was again accepted.
class Solution {
public:
int minSteps(int n) {
vector<int>dp;
for(int i=0;i<n+1;i++)dp.push_back(0);
for(int i=2;i<n+1;i++){
if(isPrime(i))dp[i]=i;
else dp[i] =dp[highestDivisor(i)]+(i/highestDivisor(i));
}
return dp[n];
}
int highestDivisor(int n) {
if (n <= 1) return -1; // No proper divisor exists for 0 or 1
for (int i = n / 2; i >= 1; i--) {
if (n % i == 0) {
return i; // First divisor found from the top is the highest
}
}
return -1; // Should never reach here for n > 1
}
bool isPrime(int n) {
if (n <= 1) return false; // 0 and 1 are not prime
if (n <= 3) return true; // 2 and 3 are prime
if (n % 2 == 0 || n % 3 == 0) return false; // eliminate multiples of 2 and 3
// Only check up to √n using 6k ± 1 optimization
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
};
Feeling very proud, I decided to try in javascript, I tried the following but saw that it was rejected.
var minSteps = function(n) {
const []dp;
for(let i=2;i<n+1;i++){
let highestDivisor=i;
for(let j=i/2;j>1;j--){
if(i%j==0){
highestDivisor=j;
break;
}
}
if(highestDivisor==i)dp[i]=i;
else dp[i] =dp[highestDivisor]+(i/highestDivisor);
}
return dp[n];
};
I got a runtime error and was flabbergasted. I decided to come back later and to first attempt an optimized java solution. I decided to come up with the following approach. Instead of determining if a number is prime to find the highest divisor. I used the following which was accepted.
class Solution {
public int minSteps(int n) {
int []dp= new int[n+1];
for(int i=2;i<n+1;i++){
if(isPrime(i))dp[i]=i;
else {
//System.out.println
dp[i] =dp[highestDivisor(i)]+(i/highestDivisor(i));
}
}
return dp[n];
}
public int highestDivisor(int n) {
if (n <= 1) return -1; // No proper divisor exists for 0 or 1
for (int i = n / 2; i >= 1; i--) {
if (n % i == 0) {
return i; // First divisor found from the top is the highest
}
}
return -1; // Should never reach here for n > 1
}
public boolean isPrime(int n) {
if (n <= 1) return false; // 0 and 1 are not prime
if (n <= 3) return true; // 2 and 3 are prime
if (n % 2 == 0 || n % 3 == 0) return false; // eliminate multiples of 2 and 3
// Only check up to √n using 6k ± 1 optimization
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
}
It was accepted and was slightly better than the original. I felt happy. I decided to retry the javascript solution. I attempted to debug using print statements and realized that j was initialized as 1.5.So,I made some changes. I used j=i-1 and reran and came up with this solution which was accepted!!! I felt I was on a roll!!!
var minSteps = function(n) {
const dp=[];
for(let i=0;i<n+1;i++)dp.push(0);
for(let i=2;i<n+1;i++){
let highestDivisor=i;
for(let j=i-1;j>1;j--){
if(i%j==0){
highestDivisor=j;
break;
}
}
if(highestDivisor==i)dp[i]=i;
else dp[i] =dp[highestDivisor]+(i/highestDivisor);
}
return dp[n];
};
5. Lessons Learned
This experience has taught me/helped reinforce a number of lessons.
1) Fully understand the problem a program/coding challenge is trying to solve by careful reading, asking the necessary questions. A problem cant be solved if you have misunderstood or dont understand it.
2) Research how previous or similar problems were solved by other programmers.
3) Develop a first draft solution to the problem.
4) If stuck, take a break. Solutions can come when your mind is at rest.
5) Optimize your solutions where possible. It can save time and memory. In production environments, this can make a noticeable difference.
6) Different programming languages handle variables differently. Understand how.
7) Debugging with print statements is an unsophisticated but simple way to troubleshoot.
6. Wrap-Up
I hope my post has been helpful, please feel free to like,comment and share. Please check out my github profile for this and more solutions.It is here : https://github.com/HectorwTT
Top comments (0)