2 Keys Keyboard

Leetcode Problem:

• 2 Keys Keyboard

Summary

• The problem is to find the minimum number of operations required to have the character 'A' exactly n times on the screen, given the ability to copy and paste characters.

Approach

• The approach used is to use a queue to store the nodes representing the state of the notepad, where each node contains the number of actions taken, the number of copied characters, and the number of 'A's on the screen
• The algorithm starts with the initial state (one 'A' on the screen) and explores all possible next states by either copying or pasting characters, and keeps track of the minimum number of actions required to reach the desired state.

Complexity

• The time complexity of the solution is O(n^2), where n is the number of 'A's on the screen, as each node is visited at most once.

Explain

• The solution uses a queue to store the nodes representing the state of the notepad
• Each node contains the number of actions taken (actionCnt), the number of copied characters (copiedCnt), and the number of 'A's on the screen (aCnt)
• The algorithm starts with the initial state (one 'A' on the screen) and explores all possible next states by either copying or pasting characters
• The next states are added to the queue if they have not been visited before
• The algorithm stops when it reaches the desired state (n 'A's on the screen) and returns the minimum number of actions required to reach that state.

Solution Code:

struct Node{
    int actionCnt;
    int copiedCnt;
    int aCnt;
};

class Solution {
public:
    queue que;
    bool visited[2001][2001];
    int minSteps(int n) {
        que.push({0, 0, 1});
        visited[0][1] = true;
        while(!que.empty()){
            Node nod = que.front();
            que.pop();
            if (nod.aCnt == n){
                return nod.actionCnt;
            }
            int nextCopied = nod.aCnt;
            int nextAcnt = nod.aCnt + nod.copiedCnt;
            if (nextCopied <= 1000 && !visited[nextCopied][nod.aCnt]){
                visited[nextCopied][nod.aCnt] = true;
                que.push({nod.actionCnt + 1,nextCopied, nod.aCnt });
            }
            if (nextAcnt <= 1000 && !visited[nod.copiedCnt][nextAcnt]){
                visited[nod.copiedCnt][nextAcnt] = true;
                que.push({nod.actionCnt + 1,nod.copiedCnt, nextAcnt });
            }
        }
        return 0;
    }
};