diff options
-rw-r--r-- | replace_non_coprime_nums.c | 56 | ||||
-rw-r--r-- | replace_non_coprime_nums.py | 36 |
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])) |