diff options
author | Jack Sangdahl <[email protected]> | 2024-11-10 19:57:18 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-10 19:57:18 -0700 |
commit | dacbeda607c789556c3d1b906a1e2f93ef5a0a65 (patch) | |
tree | c33f018bb05fc3621802868992dc173486ef6bce | |
parent | e98975046f19e250c4a6a9e8987544fc95328da1 (diff) | |
download | leetcode-dacbeda607c789556c3d1b906a1e2f93ef5a0a65.tar.gz leetcode-dacbeda607c789556c3d1b906a1e2f93ef5a0a65.zip |
2601. prime subtraction operation
-rw-r--r-- | prime_subtraction_operation.c | 46 | ||||
-rw-r--r-- | prime_subtraction_operation.py | 46 |
2 files changed, 92 insertions, 0 deletions
diff --git a/prime_subtraction_operation.c b/prime_subtraction_operation.c new file mode 100644 index 0000000..0bbb9c7 --- /dev/null +++ b/prime_subtraction_operation.c @@ -0,0 +1,46 @@ +// 2601. Prime Subtraction Operation +#include "leetcode.h" + +/* + * given a 0-indexed integer array 'nums' of length 'n'. you can perform the + * following operation as many times as you want: pick an index 'i' that you + * have not picked before, and pick a prime 'p' strictly less than 'nums[i]' + * then subtract 'p' from 'nums[i]'. return true if you can make 'nums' a + * strictly increasing array using the above operation, and false otherwise. a + * strictly increasing array is an array whose each element is strictly greater + * than its precedingelement + */ + +bool prime(int n) { + if (n <= 1) + return false; + for (int i = 2; i * i <= n; i++) + if (!(n % i)) + return false; + return true; +} + +bool primeSubOperation(int *nums, int numsSize) { + for (int i = numsSize - 2; i >= 0; i--) { + if (nums[i] >= nums[i + 1]) { + int diff = nums[i] - nums[i + 1]; + diff++; + while (1) { + if (prime(diff)) + break; + diff++; + } + if (diff >= nums[i]) + return false; + nums[i] -= diff; + } + } + return true; +} + +int main() { + int n1[] = {4, 9, 6, 10}, n2[] = {6, 8, 11, 12}, n3[] = {5, 8, 3}; + printf("%d\n", primeSubOperation(n1, ARRAY_SIZE(n1))); // expect: 1 + printf("%d\n", primeSubOperation(n2, ARRAY_SIZE(n2))); // expect: 1 + printf("%d\n", primeSubOperation(n3, ARRAY_SIZE(n3))); // expect: 0 +} diff --git a/prime_subtraction_operation.py b/prime_subtraction_operation.py new file mode 100644 index 0000000..c4216c1 --- /dev/null +++ b/prime_subtraction_operation.py @@ -0,0 +1,46 @@ +# 2601. Prime Subtraction Operation + +""" +given a 0-indexed integer array 'nums' of length 'n'. you can perform the +following operation as many times as you want: pick an index 'i' that you +have not picked before, and pick a prime 'p' strictly less than 'nums[i]' +then subtract 'p' from 'nums[i]'. return true if you can make 'nums' a +strictly increasing array using the above operation, and false otherwise. a +strictly increasing array is an array whose each element is strictly greater +than its precedingelement +""" + + +class Solution(object): + def prime(self, n): + if n <= 1: + return False + for i in range(2, int(n**0.5) + 1): + if n % i == 0: + return False + return True + + def primeSubOperation(self, nums): + """ + :type nums: List[int] + :rtype: bool + """ + p = 0 + for i in nums: + if i <= p: + return False + n = i - p - 1 + while n > 0 and not self.prime(n): + n -= 1 + if n == 0: + p = i + else: + p = i - n + return True + + +if __name__ == "__main__": + obj = Solution() + print(obj.primeSubOperation(nums=[4, 9, 6, 10])) + print(obj.primeSubOperation(nums=[6, 8, 11, 12])) + print(obj.primeSubOperation(nums=[5, 8, 3])) |