# 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 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;
}

-
Hi! I was about to send this over from Programmers when I noticed you posted it yourself. Please don't post the same question on multiple sites, we can move questions to the more suitable site automatically and we were just waiting confirmation from the Code Review mods that this is actually a good question for the site. I know someone commented pointing you here from Programmers, but, you know, they could have been wrong ;) –  Yannis Aug 24 '12 at 19:41
Please format your code nicely to make it easier for everyone else to read. You only need to format it once, but you'll save a lot of people time and increase your chances of getting feedback. Also, you typically post here when the code is already working to get a review. SO is where you take it when it doesn't work yet. –  David Harkness Aug 26 '12 at 8:47

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);

-
But this raises the complexity to O(n^2) in the worst case and wont be valid answer to the problem right? –  Jason Blake Aug 25 '12 at 3:27
I will think along your lines and come up with a suggestion maybe :) –  Jason Blake Aug 25 '12 at 3:28
No, it's O(n); it's got a single loop, col = 0 to n-1. (while the column value goes from 0 to n, the row value goes from n-1 to 0 at the same time; it's not a nested loop but a linked value.) –  Hellion Aug 25 '12 at 4:04
In fact I believe it'll take n operations in the best case, and 2n operations in the worst case. –  Hellion Aug 25 '12 at 4:07
But The code gives the wrong result, so maybe the algorithm needs some tuning - I implemented for this matrix 1111 1111 1100 1000 here is the code I used - –  Jason Blake Aug 25 '12 at 9:41

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

-

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.

-