0
$\begingroup$

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: enter image description here

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

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

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

1 Answer 1

1
$\begingroup$

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'$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – GOATNine
    Oct 28, 2021 at 19:21

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.