# Finding triples that satisfy given constraints in $O (n \log n)$ time

Given a string comprised solely of the characters $\text{a, b, c}$ we want to know the number of different $(i, j, k)$ triples such that $0 \leq i,j, k < n \text{ (here n denotes the length of the string)}$ satisfying the following two conditios :

$\bullet \text{ }s[i] = "a", s[j] ="b" \text{ and } s[k] = "c"$

$\bullet \text{ } (j + 1)^2 = (i+1)(k + 1)$

We consider such two tuples, $(i, j, k)$ and $(x, y, z)$ to be different only of $i \neq x$ or $j \neq y$ or $k \neq z$.

Example case and solution : The string $"ccaccbbbaccccca"$ with $n = 15$. There are two triplets that satisfy the given constraints, namely $(2, 5, 11)$ and $(8, 5, 3)$.

The second solution shows that $i$ is not necessarily less than $k$.

I know this is a programming question, but I'm more inclined to look for a mathematical approach that I currently seem to be missing. Since $n$ could be as large as $5 \cdot 10^5$ brute force is not feasible.

I've attempted coming by the solution by noticing that in order for $\sqrt{(i + 1)(k + 1) } = (j +1 ) \in \mathbb{N}$, $k +1$ should be of the form $(i + 1) \cdot \alpha^2$ or of the form $\frac{\alpha^2}{i + 1}$.

Hence, we would have to iterate and test in order to find the $\alpha$ values that would satisfy our conditions. Later on, I found out by inspecting the process that the latter form covers all the solutions, multiple times, so I would only need to look for answers by using the second form.

This still led to a temporal complexity of $O(\sqrt{n} \cdot \sum_{k=1}^{n}\sqrt{k})$.

I've been at this for too many hours and I have no idea how to proceed. How would you solve this? I'm guessing $O(n)$ isn't possible but $O(n \log n)$ should probably do the trick.

• Interesting exercise. Can you credit the source of this problem? Where did you encounter this?
– D.W.
Commented May 19, 2017 at 5:42

Let us shift all of your indices by $1$. The condition on the indices then becomes $j^2 = ik$. The number of factorizations of $j^2$ into $i \cdot k$ is at most $d(j)^2$, where $d(j)$ is the number of divisors of $j$. Therefore the total number of potential triples $(i,j,k)$ is at most $$\sum_{j=1}^n d(j)^2 = O(n\log^3 n).$$ (For the estimate, see this question on Mathoverflow.) Note that the actual number of triples can also be bounded by $\sum_{j=1}^n d(j^2)$, which could be smaller (and it could be yet smaller even than this sum).
This means, at the very least, that if you know $n$ in advance, then you can make a list of $\tilde{O}(n)$ triples, and solve the problem in time $\tilde{O}(n)$. Using a sieve of Eratosthenes, you can likely also calculate the triples in $\tilde{O}(n)$; it might be worthwhile to store all primes at most $500,000$ ahead of time.