Devise an algorithm of complexity O(N) finding No of 1's from a 2 dimensional matrix[N][N] containing 1's and 0's

Question

Assume a 2d [n][n] Matrix of 1's and 0's/ All the 1's in any row should come before 0's/The number of 1's in any row i should be atleast the no of 1's row (i+1). find a method and write a c program to count the no of 1's in a 2 d matrix.The complexity of the algorithm should be order n.

The Question is from Cormen's Algorithm Book and here below is my implementation for this problem.Kindly point out the mistakes in my algorithm and Hopefully suggest me a better way .Thanks!

 #include<stdio.h>
 #include<stdlib.h>

  int **map;
  int getMatrix();

   main()
 {   
  int row,col,sum,n;

   n=getMatrix();
    sum=0;
   row = n-1;      // start at bottom row 
    for (col=0; col<n; col++) {   // read columns from left to right
     while ((row >= 0) && (map[row,col] == 0)) {   // while not out of    rows, and on a 0
    sum += col;  //add count of 1s to total
    row--;       //move to next row up
}
// do nothing if we're on a 1, just move to next column.
} 
if (row >= 0)
  sum += (row+1)*col; // add in any leftover rows of all 1s
 printf("sum is %d\n",sum);

 }

 int getMatrix()
{
 FILE *input=fopen("matrix.txt","r");
char c;
 int nVer=0,i,j;
 while((c=getc(input))!='\n')
     if(c>='0' && c<='9')
        nVer++;
  map=malloc(nVer*sizeof(int*));
  rewind(input);
   for(i=0;i<nVer;i++)
  {
    map[i]=malloc(nVer*sizeof(int));
     for(j=0;j<nVer;j++)
    {
        do
        {
            c=getc(input);
        }while(!(c>='0' && c<='9'));                  
        map[i][j]=c-'0';
     } 
  }
 fclose(input);
 return nVer;
  } 

Answer 1

I think your main loop should be something more along the lines of

row = n-1;      // start at bottom row 
for (col=0; col<n; col++) {   // read columns from left to right
    while ((row >= 0) && (map[row,col] == 0)) {   // while not out of rows, and on a 0
        sum += col;  //add count of 1s to total
        row--;       //move to next row up
    }
    // do nothing if we're on a 1, just move to next column.
}
if (row >= 0) sum += (row+1)*col; // add in any leftover rows of all 1s
printf("sum is %d\n",sum);

Answer 2

Solved ,just start from the reverse end and look for the first 1, then count in each row will be the coloumn no :)

Answer 3

Sorry, but your solution is still O(N^2). Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan N-i positions in each row, for a total of N^2/2 actions, i.e. O(N^2). visually:

1* 0* 0* 0* 0*
1  1* 0* 0* 0*
1  1  1* 0* 0*
1  1  1  1* 0*
1  1  1  1  1*

Where the *s indicate you looked at that position. With smart enough code, you could actually infer the 1s, but that's still O(N^2) and probably more overhead than it's worth.

A faster solution is to find the border between 0 and 1 by binary search.

int findFirstZero(int *row, int left, int right) 
{
    if(row[right]) return right;
    int lastOne = left;
    int firstZero = right;
    int pos;
    while(firstZero - lastOne > 1) {
        pos = (lastOne + firstZero) / 2;
        if(pos) {
            lastOne = pos;
        } else {
            firstZero = pos;
        }
    }
    return firstZero;
}

int sumOnes(int **map) {
    int sum = 0;
    for(int i = 0; i < N; i++) {
        sum += findFirstZero(map[i], i, N-i-1);
    }
    return sum;
}

Now, this is actually O(NlogN), but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.