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

Question

2 years ago

15

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.

Computers and Technology

1 answer:

Anna71 [15] · Answer 1 · 2023-08-26T22:57:42+03:00

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