Last updated on October 5th, 2024 at 09:06 pm

Here, We see 2 Keys Keyboard LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

2 Keys Keyboard LeetCode Solution

Problem Statement

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

1. 2 Keys Keyboard LeetCode Solution C++

class Solution {
public:
    int minSteps(int n) {
        if(n == 1) return 0;
        int count = 0;
        bool *isPrime = new bool[n + 1];
        for(int i = 2; i < n + 1; i++) isPrime[i] = true;
        for(int i = 2; i < n + 1; i++)
        {
            if(isPrime[i] == true)
            {
                while(n % i == 0)
                {
                    count += i;
                    n /= i;
                }
                for(int j = i * i; j < n + 1; j += i) 
                {
                    if(isPrime[j]) isPrime[j] = false;
                }
            }
        }
        return count;
    }
};

2. 2 Keys Keyboard Leetcode Solution Java

class Solution {
    public int minSteps(int n) {
        Integer[][] dp = new Integer[n + 1][n + 1];
        return countSteps(n, 0, 1, 0, dp);
    }
    private int countSteps(int n, int clipBoard, int document, int steps, Integer[][] cache) {
        if (document == n) {
            return steps;
        }
        if (document > n || clipBoard > n) return Integer.MAX_VALUE;
        if (cache[clipBoard][document] != null) return cache[clipBoard][document];
        int copy = Integer.MAX_VALUE;
        int paste = Integer.MAX_VALUE;
        if (document != clipBoard) {
            copy = countSteps(n, document, document, steps + 1, cache);
        }
        if (clipBoard > 0)
            paste = countSteps(n, clipBoard, document + clipBoard, steps + 1, cache);
        cache[clipBoard][document] = Math.min(copy, paste);
        return cache[clipBoard][document];        
    }
}

3. 2 Keys Keyboard Solution JavaScript

var minSteps = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 0;
    dp[1] = 0;
    for (let i = 2; i <= n; i++) {
        dp[i] = i;
        for (let j = Math.floor(i / 2); j >= 1; j--) {
            if (i % j === 0) {
                dp[i] = dp[j] + (i / j);
                break;
            }
        }
    }
    return dp[n];
};

4. 2 Keys Keyboard Solution Python

class Solution(object):
    def minSteps(self, n):
        cache = {}
        def helper(screen, clipboard):
            if (screen, clipboard) in cache: return cache[(screen, clipboard)]
            if screen == n: return 0
            if screen > n: return float("Inf")
            copy_paste = helper(screen+screen, screen) + 2
            paste = float("Inf")
            if clipboard:
                paste = helper(screen + clipboard, clipboard) + 1
            cache[(screen, clipboard)] = min(copy_paste, paste)    
            return cache[(screen, clipboard)]
        return helper(1, 0)