Find Smallest Split Index for Coprime Products in an Array

#include #include

using namespace std;

int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); }

int findSplit(int nums[], int n) { int left_prod = nums[0]; int right_prod = 1;

for (int i = 1; i < n; i++) 
    right_prod *= nums[i]; 

if (gcd(left_prod, right_prod) == 1) 
    return 0; 

for (int i = 1; i < n - 1; i++) 
{
    // calculate the left product 
    left_prod *= nums[i]; 

    // calculate the right product 
    right_prod = 1; 
    for (int j = i + 1; j < n; j++) 
        right_prod *= nums[j]; 

    // if the gcd of products is 1, 
    // then we find the required split 
    if (gcd(left_prod, right_prod) == 1) 
        return i; 
}

// if there is no valid split 
return -1; 

}

int main() { int nums[] = {2, 3, 3}; int n = sizeof(nums) / sizeof(nums[0]);

cout << findSplit(nums, n); 

return 0; 

}