Eu tenho uma matriz que se parece com isso:

| 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 |

Eu deveria encontrar se esta matriz tem uma coluna preenchida com todos os 1. Nesta matriz é a coluna 4. E é dito que a complexidade do tempo é O (n) e a memória é O (1).

Essa matriz representa uma relação binária em um conjunto (de pessoas).n é o tamanho do conjunto, então o tamanho da matriz én * n.

Eu posso ver duas soluções possíveis:

Pegue a primeira coluna, passe por ela, veja zero, pule na próxima coluna e assim por diante. Mas o pior caso deste algoritmo será O (n2);O próximo, se eu tiver uma soma de todas as colunas, posso dar uma resposta em O (n). Mas não é dito em condições de tarefa que calculamos somas. E se eu vou computá-los, a complexidade também será O (n2);

Alguma outra solução?