{"id":599,"date":"2023-11-27T06:24:01","date_gmt":"2023-11-27T06:24:01","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=599"},"modified":"2023-12-08T13:04:24","modified_gmt":"2023-12-08T13:04:24","slug":"2-keys-keyboard","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/2-keys-keyboard\/","title":{"rendered":"2 Keys Keyboard Problem (C++, Java, Python)"},"content":{"rendered":"\n<p>In this article, we will try to solve the 2 keys keyboard problem. It is an interesting leetcode problem because the most efficient way to solve it often requires dynamic programming or mathematical insight to minimize the number of operations. The main idea is to notice the best way to do things in order to get n number of&nbsp; &#8216;A&#8217;. We will figure out how to use the copy and paste operations strategically to reach the desired number of &#8216;A&#8217;s with the minimum steps.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the 2 Keys Keyboard Problem?<\/strong><\/h2>\n\n\n\n<p>The problem typically involves a notepad with only one character, &#8216;A&#8217;, initially present, the allowed operations are:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Copy all the characters on the screen.<\/li>\n\n\n\n<li>Paste the characters that were copied last time.<\/li>\n<\/ul>\n\n\n\n<p><strong>The main goal of the 2 keys problem is to find the minimum number of operations needed to obtain exactly \u2018n\u2019 \u2018A\u2019s on the screen using the copy-and-paste operation<\/strong><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Dynamic Programming Approach<\/strong><\/h2>\n\n\n\n<p>We have a notepad and we can perform two operations copying all the characters and pasting them. We will try to solve it using the <a href=\"https:\/\/favtutor.com\/blogs\/dynamic-programming\">dynamic programming<\/a>.<\/p>\n\n\n\n<p>Let us understand it with an example,<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><strong>Input<\/strong>: n = 3<br><strong>Output<\/strong>:  3<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"262\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-5-1024x262.png\" alt=\"Example of 2 key keyboard\" class=\"wp-image-600\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-5-1024x262.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-5-300x77.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-5-768x197.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-5-750x192.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-5-1140x292.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-5.png 1276w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<p>In step 1, we use the Copy All operation.<\/p>\n\n\n\n<p>In step 2, we use the Paste operation to get &#8216;AA&#8217;.<\/p>\n\n\n\n<p>In step 3, we use the Paste operation to get &#8216;AAA&#8217;.<\/p>\n\n\n\n<p><strong>Steps to solve 2 keys keyboard problem:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Let&#8217;s start with the base case, where &#8216;n&#8217; is 1. In this case, we already have one &#8216;A&#8217; on the notepad, so no operations are needed. So the answer is 0.<\/li>\n\n\n\n<li>Now, let&#8217;s consider the case where &#8216;n&#8217; is 2. We will start with one &#8216;A&#8217;. To get two &#8216;A&#8217;s, you can perform a copy and then a paste. So the answer is 2.<\/li>\n\n\n\n<li>As we go on, we will observe a pattern. For example, to get three &#8216;A&#8217;s, you can copy the one &#8216;A&#8217; you have and then paste it. To get four &#8216;A&#8217;s, you can copy the two &#8216;A&#8217;s you have and then paste. It&#8217;s like doubling the number of &#8216;A&#8217;s each time.<\/li>\n\n\n\n<li>We will initialize a dp array of size n+1 to follow 1-based indexes to store minimum operations&nbsp;<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"241\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/4-4-1024x241.png\" alt=\"initialize dp array\" class=\"wp-image-602\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/4-4-1024x241.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/4-4-300x71.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/4-4-768x181.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/4-4-750x176.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/4-4-1140x268.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/4-4.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will initialize base case dp[1] = 0<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"222\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-5-1024x222.png\" alt=\"initialize base case dp[1] = 0\" class=\"wp-image-603\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-5-1024x222.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-5-300x65.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-5-768x166.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-5-750x162.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-5-1140x247.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-5.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>We will run two loops to fill the dp array with the minimum value till n\n<ul class=\"wp-block-list\">\n<li>The outer loop runs from 2 to n, considering each possible count of &#8216;A&#8217;s on the notepad.<\/li>\n\n\n\n<li>outer loop runs from 2 to n, considering each possible count of &#8216;A&#8217;s on the notepad.<\/li>\n\n\n\n<li>If i is divisible by j, it means we can copy &#8216;j&#8217; &#8216;A&#8217;s and paste it i\/j times to get &#8216;i&#8217; &#8216;A&#8217;s.<\/li>\n\n\n\n<li>The dp[i] is updated with the minimum of its current value and the calculated value using dp[j] + i \/ j.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now dp[n] is our ans as we were storing minimum values always<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"270\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-5-1024x270.png\" alt=\"answer is dp[n]\" class=\"wp-image-604\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-5-1024x270.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-5-300x79.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-5-768x202.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-5-750x198.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-5-1140x300.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-5.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Below is the complete C++ program to solve the 2 keys keyboard problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint minOperations(int n) {\n    if (n == 1) {\n        return 0; \/\/ Base case: already have one 'A'\n    }\n\n    vector&lt;int&gt; dp(n+1, INT_MAX); \/\/ Dynamic programming array to store minimum operations\n\n    dp[1] = 0; \/\/ Base case\n\n    for (int i = 2; i &lt;= n; i++) {\n        for (int j = 1; j &lt; i; j++) {\n            if (i % j == 0) {\n                \/\/ If 'i' is divisible by 'j', it means we can copy 'j' 'A's and paste it i\/j times to get 'i' 'A's\n                dp[i] = min(dp[i], dp[j] + i \/ j);\n            }\n        }\n    }\n\n    return dp[n];\n}\n\nint main() {\n    int n = 3;\n    int result = minOperations(n);\n    cout &lt;&lt; &quot;Minimum number of operations to get &quot; &lt;&lt; n &lt;&lt; &quot; 'A's: &quot; &lt;&lt; result &lt;&lt; endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Check the Java program to solve the problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\npublic class MinOperations {\n\n    public static int minOperations(int n) {\n        if (n == 1) {\n            return 0; \/\/ Base case: already have one 'A'\n        }\n\n        int[] dp = new int[n + 1];\n        Arrays.fill(dp, Integer.MAX_VALUE); \/\/ Dynamic programming array to store minimum operations\n\n        dp[1] = 0; \/\/ Base case\n\n        for (int i = 2; i &lt;= n; i++) {\n            for (int j = 1; j &lt; i; j++) {\n                if (i % j == 0) {\n           \/\/ If 'i' is divisible by 'j', it means we can copy 'j' 'A's and paste it i\/j times to get 'i' 'A's\n                    dp[i] = Math.min(dp[i], dp[j] + i \/ j);\n                }\n            }\n        }\n\n        return dp[n];\n    }\n\n    public static void main(String[] args) {\n        int n = 3;\n\n        int result = minOperations(n);\n\n        System.out.println(&quot;Minimum number of operations to get &quot; + n + &quot; 'A's: &quot; + result);\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Check the Python program to solve the problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def min_operations(n):\n    if n == 1:\n        return 0  # Base case: already have one 'A'\n\n    dp = [float('inf')] * (n + 1)  # Dynamic programming array to store minimum operations\n\n    dp[1] = 0  # Base case\n\n    for i in range(2, n + 1):\n        for j in range(1, i):\n            if i % j == 0:\n                # If 'i' is divisible by 'j', it means we can copy 'j' 'A's and paste it i\/j times to get 'i' 'A's\n                dp[i] = min(dp[i], dp[j] + i \/\/ j)\n\n    return dp[n]\n\nif __name__ == &quot;__main__&quot;:\n    n = 3\n    result = min_operations(n)\n    print(f&quot;Minimum number of operations to get {n} 'A's: {result}&quot;)<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>Minimum number of operations to get 3 'A's: 3<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Complexity Analysis<\/strong><\/h3>\n\n\n\n<p>The time complexity for the above code to solve the 2 keys keyboard problem is O(n<sup>2<\/sup>) as the outer loop runs \u2018n-1\u2019 and the inner loop runs &#8216;i-1&#8217; times for each iteration of the outer loop and operations inside the loops are taking constant times<\/p>\n\n\n\n<p>The space complexity for the above code is O(n) as we have declared a dp array of size (n+1), the space used scales linearly with the input size n.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>The aim of the <a href=\"https:\/\/leetcode.com\/problems\/2-keys-keyboard\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> 2 keys keyboard is to find the minimum number of operations needed to obtain exactly \u2018n\u2019 \u2018A\u2019s on the screen using the copy-and-paste operation.<strong> <\/strong>In this article, we discussed how the dynamic programming approach efficiently solves the problem and we have discussed C++, Java, and Python code to solve this problem.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Learn how to solve the leetcode problem of 2 keys keyboard using dynamic programming in C++, Java, and Python.<\/p>\n","protected":false},"author":12,"featured_media":607,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[25,14,15],"class_list":["post-599","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dp","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/599","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=599"}],"version-history":[{"count":8,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/599\/revisions"}],"predecessor-version":[{"id":867,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/599\/revisions\/867"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/607"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=599"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=599"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=599"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}