Tengo una matriz que se parece a esto:

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

Debería encontrar si esta matriz tiene una columna con todos 1. En esta matriz es la columna 4. Y se dice que la complejidad del tiempo es O (n) y la memoria es O (1).

Esta matriz representa una relación binaria en un conjunto (de personas).n es el tamaño del conjunto, por lo que el tamaño de la matriz esn * n.

Puedo ver 2 posibles soluciones:

Tome la primera columna, vaya a través de ella, si ve cero, salte en la siguiente columna y así sucesivamente. Pero el peor caso de este algoritmo será O (n2);La siguiente, si tengo una suma de todas las columnas, puedo dar una respuesta en O (n). Pero no se dice en condiciones de tarea que hemos calculado sumas. Y si los computo, la complejidad será también O (n2);

¿Alguna otra solución?