diff options
author | Jack Sangdahl <[email protected]> | 2024-07-06 14:32:54 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-07-06 14:32:54 -0600 |
commit | 203c89450fa570f342e23fe4ae9cc0b58dac5140 (patch) | |
tree | c87b86325be382975aa62760f1e64ce1625d7718 | |
parent | 70b4a51a14501dec1508a696fae824059dcd1ac5 (diff) | |
download | leetcode-203c89450fa570f342e23fe4ae9cc0b58dac5140.tar.gz leetcode-203c89450fa570f342e23fe4ae9cc0b58dac5140.zip |
650. 2 keys keyboard
-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)) |