aboutsummaryrefslogtreecommitdiff
path: root/replace_non_coprime_nums.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-15 20:30:09 -0600
committerJack Sangdahl <[email protected]>2025-09-15 20:30:09 -0600
commitb7cd5b2d6cb9a619e68bc518a369b5461cc72097 (patch)
treef694d0cc0b9a1930dfc888462a282db5031f6b6e /replace_non_coprime_nums.c
parent01c6cf8af910f8e58ece342b45b22abcc8e498f4 (diff)
downloadleetcode-b7cd5b2d6cb9a619e68bc518a369b5461cc72097.tar.gz
leetcode-b7cd5b2d6cb9a619e68bc518a369b5461cc72097.zip
2197. replace non-coprime numbers in array
Diffstat (limited to 'replace_non_coprime_nums.c')
-rw-r--r--replace_non_coprime_nums.c56
1 files changed, 56 insertions, 0 deletions
diff --git a/replace_non_coprime_nums.c b/replace_non_coprime_nums.c
new file mode 100644
index 0000000..2981cee
--- /dev/null
+++ b/replace_non_coprime_nums.c
@@ -0,0 +1,56 @@
+// 2197. Replace Non-Coprime Numbers in Array
+#include "leetcode.h"
+
+/*
+ * you are given an array of integers 'nums'. perform the following steps: find
+ * any two adjacent numbers in 'nums' that are non-coprime, if no such numbers
+ * are found, stop the process. otherwise, delete the two numbers and replace
+ * them with their lcm. repeat this process as long as you keep finding two
+ * adjacent non-coprime integers. return the final modified array. it can be
+ * shown that replacing adjacent non-coprime numbers in any arbitrary order will
+ * lead to the same result. two values 'x' and '' aree non-coprime if 'gcd(x, y)
+ * > 1' where 'gcd(x, y)' is the greatest common denomiator
+ */
+
+int gcd(int a, int b) {
+ while (b != 0) {
+ int tmp = b;
+ b = a % b;
+ a = tmp;
+ }
+ return a;
+}
+
+int *replaceNonCoprimes(int *nums, int numsSize, int *returnSize) {
+ int *ans = (int *)malloc(numsSize * sizeof(int)), top = 0;
+ for (int i = 0; i < numsSize; i++) {
+ int curr = nums[i];
+ while (top > 0) {
+ int prev = ans[top - 1];
+ int g = gcd(prev, curr);
+ if (g == 1)
+ break;
+ top--;
+ long long merged = (long long)prev / g * curr;
+ curr = (int)merged;
+ }
+ ans[top++] = curr;
+ }
+ *returnSize = top;
+ return ans;
+}
+
+int main() {
+ int n1[] = {6, 4, 3, 2, 7, 6, 2}, rs1;
+ int n2[] = {2, 2, 1, 1, 3, 3, 3}, rs2;
+ int *rnc1 = replaceNonCoprimes(n1, ARRAY_SIZE(n1), &rs1);
+ int *rnc2 = replaceNonCoprimes(n2, ARRAY_SIZE(n2), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", rnc1[i]); // expect: 12 7 6
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", rnc2[i]); // expect: 2 1 1 3
+ printf("\n");
+ free(rnc1);
+ free(rnc2);
+}