diff options
Diffstat (limited to 'replace_non_coprime_nums.c')
-rw-r--r-- | replace_non_coprime_nums.c | 56 |
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); +} |