title: Algorithm: how to find a column in matrix filled with all 1, time complexity O(n)?
body: <p>I have a matrix which looks like this:</p>
  
  <pre><code>| 1 | 0 | 0 | 1 | 0 |
  | 1 | 1 | 0 | 1 | 0 |
  | 1 | 0 | 1 | 1 | 0 |
  | 1 | 0 | 0 | 1 | 0 |
  | 0 | 0 | 0 | 1 | 1 |
  </code></pre>
  
  <p>I should find if this matrix has a column filled with all 1. At this matrix it's column 4. And it's said that time complexity is O(n) and memory is O(1).</p>
  
  <p>This matrix represents a binary relation on a set (of people). <code>n</code> is the size of the set, so the size of the matrix is <code>n * n</code>.</p>
  
  <p>I can see 2 possible solutions:</p>
  
  <ul>
  <li>Take the first column, go through it, if see zero, jump on the next column and so on. But the worst case of this algorithm will be O(n<sup>2</sup>);</li>
  <li>The next one, if I will have a sum of all columns than I can give an answer in O(n). But it's not said at task conditions that we have computed sums. And if I will compute them, the complexity will be also O(n<sup>2</sup>);</li>
  </ul>
  
  <p>Any other solutions?</p>