leetcode

commit 203c89450fa570f342e23fe4ae9cc0b58dac5140
parent 70b4a51a14501dec1508a696fae824059dcd1ac5
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat,  6 Jul 2024 14:32:54 -0600

650. 2 keys keyboard

Diffstat:
A
2_keys_keyboard.c
 | 
25
+++++++++++++++++++++++++
A
2_keys_keyboard.py
 | 
27
+++++++++++++++++++++++++++

2 files changed, 52 insertions(+), 0 deletions(-)
diff --git a/2_keys_keyboard.c b/2_keys_keyboard.c
@@ -0,0 +1,25 @@
+// 650. 2 Keys Keyboard
+#include "leetcode.h"
+
+/*
+ * 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 characters
+ * present on the screen (a partial copy is not allowed). 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.
+ */
+
+int minSteps(int n) {
+  const int primes[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
+  if (n <= 5)
+    return n == 1 ? 0 : n;
+  for (int i = 0; i < 11; i++)
+    if (!(n % primes[i]))
+      return primes[i] + minSteps(n / primes[i]);
+  return n;
+}
+
+int main() {
+  printf("%d\n", minSteps(3)); // expect: 3
+  printf("%d\n", minSteps(1)); // expect: 0
+}
diff --git a/2_keys_keyboard.py b/2_keys_keyboard.py
@@ -0,0 +1,27 @@
+# 650. 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 characters
+present on the screen (a partial copy is not allowed). 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.
+"""
+
+
+class Solution(object):
+    def minSteps(self, n):
+        """
+        :type n: int
+        :rtype: int
+        """
+        for i in range(2, int(n**0.5) + 1):
+            if n % i == 0:
+                return self.minSteps(n / i) + i
+        return 0 if n == 1 else n
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minSteps(3))
+    print(obj.minSteps(1))