У меня есть матрица, которая выглядит так:

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

Я должен найти, если эта матрица имеет столбец, заполненный всеми 1. В этой матрице это 'столбец 4. И это 's сказал, что сложность по времени составляет O (n), а память - O (1).

Эта матрица представляет бинарное отношение на множестве (людей).n это размер набора, поэтому размер матрицыn * n

Я вижу 2 возможных решения:

Возьмите первый столбец, пройдите через него, если видите ноль, прыгайте на следующий столбец и так далее. Но худшим случаем этого алгоритма будет O (n2);Следующий, если у меня будет сумма всех столбцов, чем я могу дать ответ в O (n). Но это'В условиях задачи не сказано, что мы вычислили суммы. И если я их вычислю, сложность тоже будет O (n2);

Любые другие решения?