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

he could use bold or bigger text just a suggestion.

amazon is a website were you shop cosmetics such as clothes, electronics and food. amazon also makes there own thechnology such as kindle book readers and tablets or the alexa which is an inteligent ai. and they also have a streaming service which is called prime video.