Complexity Question Based on array

Question

Given an array A of size n*n, consists of 1's and 0's such that , in any row of A, all the 1's come before any 0's in that row. Assuming A is already in memory, what is the complexity of the most efficient algorithm for finding the row of A that contains the most 1's.

A.  O(n^2)

B.  O(n)

C.  O(log n)

D.  O(nlogn)

Comments

O(n)

Ref:- https://www.geeksforgeeks.org/find-the-row-with-maximum-number-1s/

Answer 1

yes O(n)

Do like this

count number of 1's in 1'st row and start count in next row from previous row number of 1's +1

Means, suppose 1st row has two 1's

then check if 2nd row 3rd element is 1 or not

If it is 1 then count how many 1's in it.

Suppose, it has 6 number of 1's

Then go 3rd row and check 7'th element ,if it is 1 then check next element otherwise go to next row

Thus time complexity O(n)