Interview Question
Country: United States
in the example you have taken number of 1's in row i is less than the number in row i+1, while the question says otherwise.
just pointing this out..it will not have much have on the answer though ( just reversing the loop condition)
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++;
}
}
}
Sorry there are 2 typos:
1. There is an extra } at the end. 2. it should be j--. It works perfectly then, giving O(n)
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