aboutsummaryrefslogtreecommitdiff
path: root/2_keys_keyboard.c
diff options
context:
space:
mode:
Diffstat (limited to '2_keys_keyboard.c')
-rw-r--r--2_keys_keyboard.c25
1 files changed, 25 insertions, 0 deletions
diff --git a/2_keys_keyboard.c b/2_keys_keyboard.c
new file mode 100644
index 0000000..f3196e4
--- /dev/null
+++ 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
+}