leetcode

commit c43702b12814d5d6d24f74a54ec7beda177d0cc6
parent 7d073950148ac9a6b3ffb747d31ea2ef13a6f361
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  2 Feb 2024 22:34:49 +0000

1 Random Problem

Diffstat:
A
Problems/0650.cpp
 | 
35
+++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 36 insertions(+), 0 deletions(-)
diff --git a/Problems/0650.cpp b/Problems/0650.cpp
@@ -0,0 +1,35 @@
+
+// DP
+class Solution {
+    static int dp[1001][1001];
+
+    int minSteps(const int n, int total, int clip) const {
+        if (total == n) return 0;
+        if (total > n) return 1000000;
+        if (total + clip > n) return 1000000;
+        if (dp[total][clip] != -1) return dp[total][clip];
+        return dp[total][clip] = min(1 + minSteps(n, total + clip, clip), 2 + minSteps(n, total * 2, total));
+    }
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int minSteps(const int n) const { return n == 1 ? 0 : 1 + minSteps(n, 1, 1); }
+};
+
+int Solution::dp[1001][1001];
+
+// Math
+class Solution {
+  public:
+    int minSteps(int n) const {
+        int res = 0, crnt = 2;
+        while (n > 1) {
+            while (n % crnt == 0) {
+                res += crnt;
+                n /= crnt;
+            }
+            crnt++;
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -419,6 +419,7 @@ for solving problems.
 |  0647  |   Medium   | [Palindromic Substrings](Problems/0647.cpp)                                                        |
 |  0648  |   Medium   | [Replace Words](Problems/0648.cpp)                                                                 |
 |  0649  |   Medium   | [Dota2 Senate](Problems/0649.cpp)                                                                  |
+|  0650  |   Medium   | [2 Keys Keyboard](Problems/0650.cpp)                                                               |
 |  0652  |   Medium   | [Find Duplicate Subtrees](Problems/0652.cpp)                                                       |
 |  0653  |    Easy    | [Two Sum IV - Input is a BST](Problems/0653.cpp)                                                   |
 |  0654  |   Medium   | [Maximum Binary Tree](Problems/0654.cpp)                                                           |