# Is there a name of this problem?

There is $$n$$ lists (of integers) of the same length. I want to find the zeros global intersections of those lists.

Example:

$$A = [4,6,3,0,7,0,0,0,1,0,0]$$

$$B = [6,6,7,1,7,0,0,0,4,0,0]$$

$$C = [2,4,7,0,7,0,0,0,3,0,0]$$

The output are the position of those intersections:

The positions are $$5, 6, 7, 9$$ and $$10$$

Other than "traversing" the list and checking element by element, is there another way ?

• What does "zeros global intersections" mean? Can you edit your question to state the task more clearly?
– D.W.
Jun 5, 2020 at 18:32

## 1 Answer

There is no asymptotically better deterministic algorithm than the one that just checks, for each position $$i=1,\dots,n$$ whether $$A[i]=B[i]=C[i]=0$$.

This is easy to see since any correct algorithm must read at least one entry per value of $$i$$. To see this, suppose that there is an instance $$I = \langle A,B,C \rangle$$ for which a correct algorithm $$\mathcal{A}$$ accesses neither of $$A[i]$$, $$B[i]$$, and $$C[i]$$, for some $$i$$.

Consider two instances $$I' = \langle A',B',C' \rangle$$ and $$I'' = \langle A'',B'',C'' \rangle$$ that are identical to $$I$$ except (possibly) for the fact that $$A'[i]=B'[i]=C'[i]=0$$ and $$A'[i]=B'[i]=C'[i]\neq 0$$. Clearly $$\mathcal{A}$$ must return the same set $$S$$ of indices on all of $$I$$, $$I'$$, and $$I''$$. If $$i \in S$$, then $$\mathcal{A}$$ fails on $$I''$$, otherwise $$\mathcal{A}$$ fails on $$I'$$.

• Why not return not (a[i] or b[i] or c[i])? No if conditionals, and true denotes a 0 in all three arrays at that position. Oct 28, 2021 at 19:21