7
$\begingroup$

Say we have two circular binary strings $a = a_0a_1...a_{n-1}$ and $b = b_0b_1...b_{n-1}$ with arbitary starting point, and define a and b are orthogonal if $\sum_{i=0}^{n-1}a_ib_i = 0$. Is there a $O(nlogn)$ algorithm can tell a rotation of such circular binary string is orthogonal to another?

$\endgroup$
7
$\begingroup$

Say we have strings $a = a_0a_1...a_{n-1}$ and $b=b_0b_1...b_{n-1}$. First concatenate $a$ with itself and remove the last character. You should get a new string $a=a_0a_1...a_{n-1}a_0a_1...a_{n-2}$. Now we are interested in substrings of size $n$ in new string $a$ that are orthogonal to $b$ (this is a very classic trick to deal with cyclic strings/arrays).

Let's reinterpret them as polynomials in the following way.

For $a=a_0a_1...a_{2n-2}$ use value at position $i$ as the coefficient associated with power $i$ in a polynomial such that $P_a(x) = a_0x^0 + a_1x^1+...+a_{2n-2}x^{2n-2}$.

Now reverse $b$ and get the new string $b=b_{n-1}...b_1b_0$ and build a polynomial similarly as we did above. You get $P_b(x)=b_{n-1}x^0+...+b_1x^{n-2}+b_0x^{n-1}$.

Now let the magic happen. Multiply both polynomials into $P(x) = P_a(x) \cdot P_b(x)$ (Remember to do this fast). Wait, what ... where is the answer to the problem.

Let's see what is the $n-1$ coefficient of the new polynomial: $$P(x) = c_0x^0+c_1x^1+...+c_{3n-3}x^{3n-3}$$

Coefficient at position $n-1$ is equal to $$c_{n-1} = a_0 \cdot b_0 + a_1 \cdot b_1 + ... a_{n-1}\cdot b_{n-1}$$

Awesome, that is the dot product of original string $b$ with original string $a$ (without rotations). Keep looking at further terms of $P$. Coefficient at position $n$ is equal to $$c_{n} = a_1 \cdot b_0 + a_2 \cdot b_1 + ... + a_{n-1} \cdot b_{n-2} + a_{n} \cdot b_{n - 1}$$

But keep in mind that $a_n=a_0$ since this is just $a$ concatenated with itself. So we have the dot product of $a$ rotated one step to the left with $b$. You can see that terms of $c_{i}$ from $n - 1 \le i \le 2n - 1$ will give you the dot product of all rotations of $a$ with array $b$. Therefore, after computing $P$, you can find whether there is at least one dot product with value equals to $0$ easily.

In general polynomial multiplication is a useful representation to model convolutions of two arrays. It turns out that a lot problems can be modeled this way in areas such as: combinatoric, dynamic programming, string matching with least mismatches.

This is indeed relevant because there is a very efficient way to multiply polynomials which is via FFT in $O(n \log n)$ (or Karatsuba in $O(n^{\frac{3}{2}})$) instead of the naive $O(n^2)$ algorithm.

$\endgroup$

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.