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.
On
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.
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).