Question

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.

Answer 1

Check the explanation

Step-by-step explanation:

• Each row of nxn array A 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.
• Use binary search algorithm to find the index of the last 1 in a row.
• Perform this process for each row.
• Now, searching for last occurrence of 1 in a row will take O (log n) time.
• There are n such rows, therefore total time will be O (n log n).

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