Suppose that each row of an n×n array A consists of 1’s and 0’s such that, in any row i of A, all the 1’s come before any 0’s in that row. Suppose further that the number of 1’s in row i is at least the number in row i+ 1, for i = 0, 1,...,n− 2. Assuming A is already in memory, describe a method running in O(n) time (not O(n2) time) for counting the number of 1’s in the array A.

Check the explanation

Explanation:

Complexity analysis:

   The method would be to use binary search for each row to find the first zero starting with index of A[i][n/2+1].

   Let’s say j=n/2.

   The number of 1’s in a row would be j+1.

   This would take O (log n).

   An algorithm that divides by 2 until the number gets sufficiently small then it terminates in O (log n) steps.

   As there are n rows the complexity would be O (n log n).

Pseudo-code:

A = [[1,0,0,0],[0,0,0,0],[1,1,1,1],[1,1,0,0]]

n=4

c=0

for i in range(n): # Loop in rows

  j = n/2 # Search from middle index

  while j>0: # Loop in column

      if(A[i][j]==0): # search for first zero

          if(A[i][j-1]==1): # confirm first zero

              c = c+j # add 1's count to c

              break

          else: # reduce index by 1 or j/2

              if(j/2 == 0):

                  j = j-1

              else:

                  j = j - j/2

      else: # increase index by 1 or j/2

      if(j/2 == 0):

      j = j+1

      else:

          j = j + j/2

      if(j==n): # For all 1's

      c = c+n

      break  

print c