## Interview Question

**Country:**United States

```
count_ones(A, n):
b = 0
for (i = 0; i < n; ++i)
if (A[n - 1][i] != '1') break
++b
c = b
for (j = n - 2; j >= 0; --j)
c += b
for (i = b; i < n; ++i)
if (A[j][i] != '1') break
++b
++c
return c
```

This is O(n). The top for-loop will run n times to count the number of 1's in the n-1 row. The bottom for-loops will run from rows n-2 to 0 counting the 1's in those rows. However, the inner-loop will only count from b to n, where b is the number of 1's in the row below it. The worst case is when the number of 1's from n-1 to 0 increase by just one per row, forcing two comparisons per row (one for the new '1', and another for the 'D' next to it). The number of comparisons made can be represented by the relation, T(n) = T(n -1) + 2. The 2 is from two comparison.

T(n) = T(n - 1) + 2

T(n - 1) = T(n - 2) + 2

T(n - 2) = T(n - 3) + 2

-------------------------------

T(n - 1) = [T(n - 3) + 2] + 2 = T(n - 3) + 4

T(n) = [T(n - 3) + 4] + 2 = T(n - 3) + 6

T(n) = T(n - i) + 2i

T(1) = 1, since one element will only require one comparison

for i = n - 1,

T(n) = T(n - (n - 1)) + 2(n - 1) = T(1) + 2n - 2 = 1 + 2n -2 = 2n - 1 = O(n)

So, O(n) + O(n) = O(n)

what will happened in this situation ?

1, 1, D, D, D, D

1, 1, 1, 1, 1, D

1, 1, 1, D, D, D

1, 1, 1, 1, 1, D

1, 1, 1, 1, 1, D

1, 1, 1, 1, 1, 1

```
int countones(int arr[][], int n) {
int prev = 0;
int count = 0;
for (int i = n-1; i > =0 ; i++) {
num+=prev;
for (int j = prev - 1; j < n; j++) {
if (arr[i][j]) {
num++;
prev++;
} else break;
}
}
```

int count = 0;

int column = 0;

for (int row = arr.length - 1; row > 0; row--) {

while (column <= arr.length - 1 && arr[row][column] == 1) {

count = count + row + 1;

column = column + 1;

}

}

```
public int countingOnes(int[][] ones){
int size = ones.length();
int counter = 0;
for(int i=0;i<size;i++){
//check for the last row because that will have max number of ones.
if(ones[size-1][i]!='1') break;
counter++;
}
int t = counter;
int j=n-2;
while(j>=0){
if(ones[j][b]!='1') break;
b++;
j++;
}
}
}
```

count_ones(A) { |MAX Times|

[row,col] = size(A); | 1 time | // Get rows and columns of Array A

result = 0; | 1 time |

i = 1 ; j = 1; | 1 time | // First element A(1,1)

for(i=1; i<=row; i++){ | N times |

while( A(i,j) != 0) |col times|

j++; |col times|

result += j; | N times |

j = 0; | N times |

}

return result; | 1 time |

}

```
count_ones(A){ |MAX Times|
[row,col] = size(A); | 1 time | // Get rows and columns of Array A
result = 0; | 1 time |
i = 1 ; j = 1; | 1 time | // First element A(1,1)
for(i=1; i<=row; i++){ | N times |
while( A(i,j) != 0) |col times|
j++; |col times|
result += j; | N times |
j = 0; | N times |
}
return result; | 1 time |
}
```

- ravio September 21, 2014