Smallest subarray problem

Say you have an array of integers like [1, 2, 3, 4, 5, 6], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement:

• sub-array.first_integer and sub-array.last_integer must have a common divisor that is not 1.

So for [7, 2, 3, 4, 5, 6] the answer would be 2, because you can break it up like  and [2, 3, 4, 5, 6], where 2 and 6 have a common divisor of 2 (which is > 1 so it meets the requirement).

You can assume the array can be huge but the numbers are not too big. Is there a way to do this in n or n*log(n) time? I think with dp and caching n^2 is possible but not sure how to do it faster.

Here is my current attempt with a BFS, but it's still N^2:

https://onlinegdb.com/ryZwkYnA8

Edit: OK I think I found an improvement which is a polynomial times the square root of a pseudo-polynomial: n * sqrt(magnitude of the values). Seems much faster, it basically builds an adjacency list; and can be done BFS, DP, and caching all the same. Although I wonder if anything better is available?

https://onlinegdb.com/SJpl4930L

• How does the first subarray satisfy the condition? There is no divisor $> 1$ of $1$. Jul 3 '20 at 9:24
• Also, what do you mean with smallest way? Do you mean the smallest number of subarrays in the decomposition? Jul 3 '20 at 9:26
• "How does the first subarray satisfy the condition? There is no divisor >1 of 1" My bad, 1 will not be in the input. Edited.
– Dave
Jul 3 '20 at 9:51
• Smallest way = How to split the original array into as small a number of subarrays as possible where all the subarrays satisfy the requirement. I updated to include my current attempt, which is a working N^2.
– Dave
Jul 3 '20 at 9:52

In my answer I will assume that all numbers are at most $$M$$ big, i.e. $$A[i] \le M$$.

Computing the GCD takes $$O(\log M)$$ time. So your first approach is actually $$O(N^2 \log M)$$. I also don't think that your second approach is actually better than $$O(N^2)$$. For instance assume if all the numbers of the first half of the array are equal. Then for each of those numbers you have at least $$\Theta(N)$$ effort for each divisor of $$N$$. Which means that the complexity for such a test case is something like $$O(N^2 \sqrt M)$$.

Let's first discuss a very trivial (but slower) dynamic programming solution, on which I will later base a better one.

Let's define the function $$f$$ as $$f(i)$$ is the smallest number of subarrays in which you can split the prefix of size $$i$$ of the array (the first $$i$$ numbers). Also let $$f(i) := \infty$$ if it is not possible to split the array, and $$f(0) := 0$$.

It's easy to see, that you can compute $$f(i)$$ using the recursion:

$$f(i) = \min_{\substack{1 \le j \le i\\ \gcd(A[i], A[j]) > 1}} f(j-1) + 1$$

This formula is very trivially to implement together with dynamic programming, and will have the complexity $$O(N^2 \log M)$$.

f(0) = 0
for i = 1 to N:
f(i) = infinity
for j = 1 to i:
if gcd(A[i], A[j]) > 1:
f(i) = min(f(i), f(j-1)) + 1
print f(N)

Now to a better approach. We need two mathematical facts that will help us:

• If two numbers have a common divisor greater than one, then they have a common prime factor.
• A number $$\le M$$ has at most $$\log M$$ prime factors.

Let the set of prime factors of $$x$$ be $$P(x)$$.

Then we can also rewrite the recursion for $$f$$ as:

$$f(i) = \min_{p \in P(A[i])} \left( \min_{\substack{1 \le j \le i\\ p ~|~ A[j]}} f(j-1) \right) + 1$$ In other word, if $$A[i] = 20 = 2^2 \cdot 5$$, then we look for all previous numbers who are divisible by 2, and take the minimum of $$f(j-1)$$, and for all previous numbers who are divisible by $$5$$ and take the minimum of $$f(j-1)$$. The actual optimal value $$f(i)$$ will one more than the minimum of both.

If we define $$g(p, i)$$ as the minimum of $$f(j-1)$$ with $$p ~|~ A[j]$$ and $$1 \le j \le i$$, then the formula simplifies to:

$$f(i) = \min_{p \in P(A[i])} g(p, i) + 1$$

We can actually apply some sort of dynamic programming also to the function $$g$$. We store the values in a hash table. First we initialize the function for every possible prime factor with $$g(p) = \infty$$, and whenever a $$f(j-1)$$ changes, we update $$g(p)$$ for every $$p \in P(A[j])$$.

This means, after we update $$f(i)$$, we only need to update $$O(\log M)$$ different values of $$g$$.

This gives us the following algorithm:

# initialize g
for all p:
g(p) = infinity

# set the first value f(0)
f(0) = 0
# update g
for p in P(A):
g(p) = min(g(p), f(0))

for i = 1 to N:
# first compute f(i)
f(i) = infinity
for p in P(A[i]):
f(i) = min(f(i), g(p)) + 1

# and then update g
if i < N:
for p in P(A[i+1]):
g(p) = min(g(p), f(i))
print f(N)

It's easy to see that this algorithm runs in $$O(N \log M)$$ time.

A shorter variation, but with the exact same approach and complexity, would also be:

for all p:
g(p) = infinity
f(0) = 0
for i = 1 to N:
f(i) = infinity
for p in P(A[i]):
g(p) = min(g(p), f(i-1))
f(i) = min(f(i), g(p)) + 1
print f(N)

The only thing to discuss is, how we get the prime factorization of each number. There are loads of different approaches. For instance if $$M$$ is not too big, you can compute the Sieve of Eratosthenes in $$O(M \log M)$$ and during the computation store a prime factor for each number $$\le M$$. This allows to compute the prime factorization of each number in $$O(\log M)$$. Another option would be just to compute the prime factors on the fly, which would give take additionally $$O(N \sqrt{M}$$) time if you use the typical trial division until square root algorithm.