aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-10 19:57:18 -0700
committerJack Sangdahl <[email protected]>2024-11-10 19:57:18 -0700
commitdacbeda607c789556c3d1b906a1e2f93ef5a0a65 (patch)
treec33f018bb05fc3621802868992dc173486ef6bce
parente98975046f19e250c4a6a9e8987544fc95328da1 (diff)
downloadleetcode-dacbeda607c789556c3d1b906a1e2f93ef5a0a65.tar.gz
leetcode-dacbeda607c789556c3d1b906a1e2f93ef5a0a65.zip
2601. prime subtraction operation
-rw-r--r--prime_subtraction_operation.c46
-rw-r--r--prime_subtraction_operation.py46
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]))