Answer:
Check the explanation
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
