Question

Suppose that each row of an n × n array A consists of 1’s and 0’s such that, in
any row of A, all the 1’s come before any 0’s in that row. Assuming A is already
in memory, describe a method running in O(n log n) time (not O(n2) time!) for
counting the number of 1’s in A.

Answer 1

the solution for this problem can be done using left binary search

left binary search is used to find the first occurrence of a number in a sorted array

we can use left binary search algorithm to find the occurrence of first zero in the array and the can subtract the index from total length to get the count of 1's in that array

it operates in o(logn) time

since it is an n*n array the total complexity is o(nlogn)

we can use the following method implemented in c to get the result:

#include<stdio.h>
#include<stdlib.h>
int countones(int *a,int n)//left bin search, works in logn time
{
   int low=0,high=n-1,mid,ind=-1;
   while(low<=high)//until we find 0
   {
       mid=(low+high)/2;//checking mid element
       if(a[mid]==0)//checking if we find 0
       {
           ind=mid;//updating mid
           high=mid-1;//finding 0 in the left part of mid
       }
       else if(a[mid]!=0)//if we find 1
           low=mid+1;
       else
           high=mid-1;
   }
   return ind==-1?n:ind;
}
int main()
{
   int a[1000][1000],n,i,j,count=0;
   printf("Enter n: ");
   scanf("%d",&n);//reading n times
   printf("enter n*n array");
   for(i=0;i<n;i++)//reading array
   {
       for(j=0;j<n;j++)
           scanf("%d",&a[i][j]);
   }
   for(i=0;i<n;i++){//repeats n times
       count+=countones(a[i],n);
   }
   printf("%d",count);
   return 0;
}

output: