Split the Array to Make Coprime Products

Split the Array to Make Coprime Products

What is this problem about?

The Split the Array to Make Coprime Products coding problem is a mathematically rigorous challenge where you are given an array of integers. Your goal is to find the smallest index $i$ such that the product of the first $i+1$ elements and the product of the remaining elements are coprime. Two numbers are coprime if their greatest common divisor (GCD) is 1, meaning they share no common prime factors.

Why is this asked in interviews?

Asked by companies like Zomato, this problem evaluates a candidate's knowledge of Number Theory and efficient Array processing. It's not just about computing products (which would lead to overflow) but about understanding prime factorization. It tests if you can move beyond naive calculations to use the properties of numbers to solve optimization problems.

Algorithmic pattern used

The primary Algorithmic pattern used is Prime Factorization combined with a Hash Table or frequency tracking. Instead of multiplying numbers, you focus on their prime factors. For a split to result in coprime products, no prime factor present in the left part of the array can be present in the right part. You can pre-calculate the first and last occurrence of every prime factor in the array. The problem then transforms into finding an index $i$ that doesn't "break" any prime factor's range.

Example explanation (use your own example)

Suppose you have the array [4, 7, 8, 15].

1. Prime factors of 4 are {2}.
2. Prime factors of 7 are {7}.
3. Prime factors of 8 are {2}.
4. Prime factors of 15 are {3, 5}. The prime factor 2 appears at index 0 and index 2. This means any split before index 2 will have the factor 2 in both the left and right products, so they won't be coprime. We must split at least after index 2. At index 2, the left part is [4, 7, 8] (factors: 2, 7) and the right part is [15] (factors: 3, 5). Since {2, 7} and {3, 5} share no factors, the GCD is 1. The smallest index is 2.

Common mistakes candidates make

• Integer Overflow: Trying to actually compute the product of the array elements.
• Slow Factorization: Factoring each number repeatedly instead of using a Sieve of Eratosthenes for pre-computation.
• Ignoring the GCD Property: Not realizing that coprime products mean zero shared prime factors.
• Incorrect Range Merging: Failing to correctly track the "span" of each prime factor from its first to its last appearance.

Interview preparation tip

Brush up on your number theory, specifically prime factorization and the Sieve of Eratosthenes. For Array, Math, Number Theory interview pattern problems, the key is often to decompose numbers into their most basic building blocks—primes.