diff options
-rw-r--r-- | 2_keys_keyboard.c | 25 | ||||
-rw-r--r-- | 2_keys_keyboard.py | 27 |
2 files changed, 52 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 +} diff --git a/2_keys_keyboard.py b/2_keys_keyboard.py new file mode 100644 index 0000000..66f274a --- /dev/null +++ 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)) |