# How to perform orthogonal check on two circular binary strings?

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?

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.