More efficient algorithm to find OR of two sets Given a matrix of n rows and m columns of 1's and 0's, it is required to find out the number of pairs of rows that can be selected so that their OR is 1111....m times.
Example:
1 0 1 0 1
0 1 0 0 1
1 1 1 1 0

Answer:
2 ---> OR of row number [1,3] and [2,3]

Given n and m can be an order upto <= 3000, how efficiently can this problem be solved?
PS: I already tried with a naive O(n*n*m) method. I was thinking of a better solution.
 A: In case you do not only want to output the number of pairs but also the pairs itself, you cannot do better than $\mathcal O(n^2m)$ in the worst case. This is because you need to read all the columns of the input anyway, hence the factor $m$, and you need to output all $\sim n^2$ pairs (in the worst case).
A: It seems easier to find the pairs you don't want.
Consider one column, find every line in that column that have a $0$ in it.
Let $I_k$ be the set of indices for that column, any pair of indices in $I_k$ forms an invalid pair.
If you initialize a set of every possible pairs, that'll cost you $\mathcal O(n^2)$ time and memory. With this initialization, it's easy to keep track of what pair you've already excluded or not.
Finding $I_k$ costs $\mathcal O(n)$, processing all pairs in $I_k$ is at worst the number of invalid pairs overall, let's say $L$. Whenever you find a new pair to exclude, you can update a global counter, or even make a list of indices (if you need to identify the valid/invalid pairs).
Repeat for all $m$ columns, overall time complexity
of $\mathcal O(n^2 + nm + Lm)$.
Because $L\le n^2$ this is always better (not worse in asymptotic cases) than the completely naive way. If every pair is valid, $L=0$. If no pair is valid, $L=\frac{n(n-1)}2$, but if you kept track of the number of pairs you can interrupt the process after the first column. So the worst case would be somewhere in the middle.
