/***
There is a 2D nxn array of 0's and 1's. Each and every row is sorted.
Now you have to report the row with max no. of zeros in O(n) time.
***/
void rowWithMaxNumberOfZeros(int **arr,int r,int c)
{
int i=0,j=0;
int optRow=0,optCol=c-1;
int found = 0;
for(j=0;j lessThan c;j++)
{
if(arr[0][j] == ONE)
{
optCol = j-1;
found = 1;
break;
}
}
if(found == 0 && j ==c)
{
optCol=c-1;
}
i++;
while(i lessThan r && (optCol+1) lessThan c)
{
if(arr[i][optCol+1] == ZERO )
{
found = 0;
for(j=optCol+1;j lessThan c;j++)
{
if(arr[i][j] == ONE)
{
found = 1;
optCol = j-1;
optRow = i;
break;
}
}
if(found == 0 && j ==c)
{
optCol=c-1;
optRow = i;
}
}
i++;
}
printf("Row containg max number of zeros is %d till this column %d\n",optRow,optCol);
}
Well mister,
ReplyDeleteI think your algorithm is not O(n).
Also, it is not tuned enough, some condition checks can be done away with. For e.g. if(found ==0 && j==c), here j==c is not required.
Since the rows r sorted all 0 come b4 1
ReplyDeletei=j=maxx0=0;
while (i<=n)
{
while (!a[i][j])
++j;
if (maxx0<j)
{maxx0=j;maxx0line=i;}
++i;
}