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 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 at least the number of 1's row (i+1). Find a method and write a C program to count the number of 1's in a 2D matrix. The complexity of the algorithm should be order n.


The question is from Cormen's Algorithm Book. Kindly point out the mistakes in my algorithm and hopefully suggest a better way.

 #include&lt;stdio.h&gt;
 #include&lt;stdlib.h&gt;

  int **map; 
   int getMatrix();

  main()
  {
   int n,i,j,t;
 j=0;
 n=getMatrix();
   i=n-1;  
    int sum[n];
   for(t=0;t&lt;n;t++)
    sum[t]=0;
int count=0; 
 while ( (i&gt;=0) &amp;&amp; (j&lt;n) )
 {
  if ( map[i][j] == 1 )
   {
    j++;
    count=count+1;
   }
  else
  {
     if (i==(n-1))
    {
        sum[i]==count;
        count=0;
    }   
    else            
    {
        sum[i]=sum[i+1]+count;
        count=0;            
        i--;
    }
  }
  }
       for (t=0;t&lt;n;t++) 
         { 
             if ((t==(n-1)) &amp;&amp; (sum[t]==0))
               sum[t]=0;
                  else if ((sum[t]==0) &amp;&amp; (sum[t+1]&gt;0))  
               sum[t]=sum[t+1];
             }
       int s=0;
          for (t=0;t&lt;n;t++)
        s=s+sum[t];
          printf("\nThe No of 1's in the given matrix is %d \n" ,s);
        } 

  int getMatrix()
 {
   FILE *input=fopen("matrix.txt","r");
 char c;
     int nVer=0,i,j;
 while((c=getc(input))!='\n')
   if(c&gt;='0' &amp;&amp; c&lt;='9')
    nVer++;
      map=malloc(nVer*sizeof(int*));
    rewind(input);
    for(i=0;i&lt;nVer;i++)
 {
  map[i]=malloc(nVer*sizeof(int));
   for(j=0;j&lt;nVer;j++)
  {
    do
    {
        c=getc(input);
    }while(!(c&gt;='0' &amp;&amp; c&lt;='9'));                  
    map[i][j]=c-'0';
} 
}
     fclose(input);
  return nVer;
  }
I think your main loop should be something more along the lines of

row = n-1;      // start at bottom row 
for (col=0; col&lt;n; col++) {   // read columns from left to right
    while ((row &gt;= 0) &amp;&amp; (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 &gt;= 0) sum += (row+1)*col; // add in any leftover rows of all 1s
printf("sum is %d\n",sum);