aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--replace_non_coprime_nums.c56
-rw-r--r--replace_non_coprime_nums.py36
2 files changed, 92 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);
+}
diff --git a/replace_non_coprime_nums.py b/replace_non_coprime_nums.py
new file mode 100644
index 0000000..8707c8d
--- /dev/null
+++ b/replace_non_coprime_nums.py
@@ -0,0 +1,36 @@
+# 2197. Replace Non-Coprime Numbers in Array
+from math import gcd
+
+"""
+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
+"""
+
+
+class Solution(object):
+ def replaceNonCoprimes(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: List[int]
+ """
+ ans = []
+ for i in nums:
+ while ans:
+ g = gcd(ans[-1], i)
+ if g == 1:
+ break
+ i = (ans.pop() * i) // g
+ ans.append(i)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.replaceNonCoprimes(nums=[6, 4, 3, 2, 7, 6, 2]))
+ print(obj.replaceNonCoprimes(nums=[2, 2, 1, 1, 3, 3, 3]))