@senthilnathan : very nice indeed
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
On Jun 7, 8:49 am, Senthilnathan Maadasamy
senthilnathan.maadas...@gmail.com wrote:
We can do it in O(n * log n) by individually binary-searching for zero on
each of the rows. Once we get the index of the first position where zero
appears, counting the number of negative number is
Actually, this might not always be the best approach. Example:
-1 1 2 3 4
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2*N = 10 steps.
With my algo, you'll go:
Step 1: top-left: negative, count++,
Step2: [0][1] non negative, set limitRow=0 (or 1 depending on how you
code)
Step3: for([i][j]
*What if there are no zero elements at all?*
*
*
*...@minotauraus Very valid question. The terminating condition for the
binary search can be modified to return the count of negative numbers in the
array instead. *
--
You received this message because you are subscribed to
@senthilnathan: Indeed a nice logic. Complexity is O(logn) worst case(if
all elements are negative).
http://codepad.org/hRbYV287
On Tue, Jun 8, 2010 at 8:18 AM, Minotauraus anike...@gmail.com wrote:
Actually, this might not always be the best approach. Example:
-1 1 2 3 4
1 2 3 4
We can do it in O(n * log n) by individually binary-searching for zero on
each of the rows. Once we get the index of the first position where zero
appears, counting the number of negative number is straight-forward.
Here is an even better O(N) algorithm which is very elegant:
Consider the
I meant O(n) considering there are n elements and not n rows/
columns. :-)
so my n = nrows x ncolumns. Since we talk of input size in terms of
number of elements
I thought it'd be n instead of nrowsXncolumns.
On Jun 6, 4:26 am, Senthilnathan Maadasamy
senthilnathan.maadas...@gmail.com wrote:
1. check arr[0][0]. If this is non negative, there are 0 negative
numbers. (assuming sorting is ascending)
2. for arr[i][j], increment j until you hit a non-negative number.
this index will be limitRow
3. increment i, until you hit a non-negative number, this index will
be limitColumn,
for
assuimg the array is sorted likeeach number below is less than the one
above and more than the one right to it
start from the bottom right ..start moving right until u reach anumber less
than zerocalcuate the num of negative elements in that row(n-current
columng pos)..and then move
