2
$\begingroup$

Given an array $A[1],\ldots,A[n]$ of natural numbers, we have to construct a new array $B[1],\ldots,B[n]$, where $B[i]$ is equal to $A[j]$ for the minimal $j > i$ such that $A[j]$ divides $A[i]$, or $-1$ if no such element exists. For example: $$ \begin{array}{c|ccccccc} A & 10 & 4 & 5 & 2 & 1 & 8 & 4 \\\hline B & 5 & 2 & 1 & 1 & -1 & 4 & -1 \end{array} $$

I can solve this in $O(n^2)$ using brute force. Is there a better solution?

$\endgroup$
3
  • $\begingroup$ Why does the last 4 have the result -1 and not +1? $\endgroup$ – gnasher729 Apr 9 '18 at 7:19
  • $\begingroup$ @gnasher729 that's because there is no element to the right of 4, which divides 4. In general, it would be -1 for the last element $\endgroup$ – nikhil Apr 9 '18 at 12:43
  • $\begingroup$ Better how? In asymptotic worst-case running time? In running time in practice? If the former, what's the model of computation? Are we allowed to do arithmetic on arbitrary-sized integers in $O(1)$ time? Transdichotomous model? How large are the input numbers? Arbitrarily large? Constant size, independent of $n$? What's the context in which you encountered this problem? Can you credit the source where you saw it? Can you explain the motivation? $\endgroup$ – D.W. Apr 9 '18 at 17:28
1
$\begingroup$

No, probably not, if you care about theoretical worst-case running time. The problem is as hard as the subset containment problem: given sets $S_1,\dots,S_n$, check whether there exists sets $S_i,S_j$ such that $S_i \subset S_j$. It's known that there is no algorithm with $O(n^{2-\epsilon})$ running time, assuming the SETH conjecture is true. Thus, any faster algorithm would imply a disproof of SETH, which is a famous open problem -- so you shouldn't expect any easy algorithm that does significantly better than $O(n^2)$ in worst-case running time. (I don't count a $\log n$ factor speedup as significant.) See https://cstheory.stackexchange.com/q/9896/5038.

If you only care about the "average case" it might be possible to do better. The answer might also depend on the model of computation and the size of the integers, so it's possible there might be some choice of those that lets you evade this hardness result.


For instance, if your numbers are "random" in a particular specific way, you can use a divide-and-conquer algorithm. First recursively solve the problem for $A[1..n/2]$, and recursively solve the problem for $A[n/2+1..n]$. Then for each $i \le n/2$ such that $B[i]=-1$, we'll find the smallest $j > n/2$ such that $A[j]$ divides $A[i]$ and overwrite $B[i]$ with $j$. Suppose we can do that last step in $U(n)$ time. Then the total running time will satisfy the recurrence $T(n) = 2 T(n/2) + U(n)$, i.e., $T(n) = O(U(n) \log n)$.

OK. So how will we do that last step? We'll solve that problem in turn using a separate divide-and-conquer algorithm. Pick a prime number $p$ that hasn't been picked yet, and construct the sets $S^0 = \{i : p \not| A[i], i \le n/2\}$, $S^1 = \{i : p | A[i], i \le n/2\}$, $T^0 = \{i : p \not| A[i], i > n/2\}$, $T^1 = \{i : p | A[i], i > n/2\}$. Now for each $i \in S^0$, find the smallest $j \in T^0$ such that $A[j]$ divides $A[i]$; and for each $i \in S^1$, find the smallest $j \in T^0$ such that $A[j]$ divides $A[i]$ (or, equivalently, such that $A[j]$ divides $A[i]/p$), and find the smallest $j \in T^1$ such that $A[j]$ divides $A[i]$ (or, equivalently, such that $A[j]/p$ divides $A[i]/p$). Those are three subproblems each of size $n/2$ (heuristically, assuming the numbers are random and half are divisible by $p$ and half aren't), and then you can combine them to get a solution to the original problem in $O(n)$ time, so the total running time to do this last step is $U(n) = 3 U(n/2) + O(n)$, which solves to $U(n) = O(n^{\lg 3}) = O(n^{1.585})$.

So, heuristically the total running time of this approach is $O(n^{1.585} \log n)$ under a particular assumption on the distribution of the numbers.

$\endgroup$
0
$\begingroup$

Tricky. You will often go much faster than $n^2$ if you check whether $x_{i-1}$, $x_{i+1}$, $x_{i-2}$, $x_{i+2}$, is a divisor of $x_i$, so the effort is proportional to n times average distance to the nearest divisor.

To go better, you might go from numbers to multiples, and try using some data structure that keeps track of multiples of 2, 3, 5, 7 etc.

$\endgroup$
2
  • $\begingroup$ Why do we need to check for xi-1 for xi. We only need to check if a nearest divisor exists to the right of the current element $\endgroup$ – nikhil Apr 9 '18 at 12:45
  • $\begingroup$ Don't write "closest" when you mean "closest to the right". That's confusing. $\endgroup$ – gnasher729 Apr 9 '18 at 21:00
0
$\begingroup$

I've given this problem some thought and I say that you might get an average running time of less than $O(n^2)$, but a theoretical time complexity of less than $O(n^2)$ is not possible. The problem explicitly calls for a dividend-divisor check between past and future elements. There is no way to effect this regardless of how diligently you keep track of divisors.

Consider an array like $45, 40, 35, 30, 25, 5$. This would yield an array of $5, 5, 5, 5, 5, -1$. There is no way for you to fill in those $5$s without looking ahead. Even if you built some kind of tree or hash the effectiveness of such a structure is only realized when dividend-divisor relationships are made.

$\endgroup$
2
  • 1
    $\begingroup$ Your argument that the problem requires $\Omega(n^2)$ is heuristic and doesn't really constitute a proof. $\endgroup$ – Yuval Filmus Apr 9 '18 at 17:39
  • $\begingroup$ whoops, you are right I meant average, not amortized. And yes it is more of a hand wavy argument as opposed to a formal proof. $\endgroup$ – Srini Apr 9 '18 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.