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?
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.
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.
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.
