leetcode

// 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);
}