How can we find an element in the matrix [n*n] which is sorted row
wise and column wise in O(log n).
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
A more general problem is discussed in Introduction to Algorithms by
Cormen et al
problem 6-3, although the running time is O(n)...
nagendra kumar wrote:
How can we find an element in the matrix [n*n] which is sorted row
wise and column wise in O(log n).
I guess it is famous Younge Tableau Problem of tableau MxN and searching
can be done in O(M+N).
I doubt the problem can be solved in O(lgn) if no space constraint and no
pre-processing constraint present.
On Thu, Aug 20, 2009 at 9:42 PM, Anil C R cr.a...@gmail.com wrote:
A more general problem
On Aug 16, 7:29 pm, Ralph Boland rpbol...@gmail.com wrote:
On Aug 14, 1:45 am, richa gupta richa.cs...@gmail.com wrote:
can we check the divisibility of a given number by 3 withoutusing
operators like '/' or '%'.
I want the efficient solution to this problem ..
can someone help ??
i can improve a bit..
my logic is that
i will take the a[n/2][n/2] element (middle of the diagonal element)
if (num_2_b_search a[n/2][n/2])
square sub matrix from a[0][0] till a[n/2][n/2] can be left out..
i mean divide the whole matrix in 4 half
A B
C D
in my above case
A is chopped off
Richa,
Did you see http://geeksforgeeks.org/?p=511
I think, above link provides the kind of solution you are looking for
On Thu, Aug 20, 2009 at 11:33 PM, Ralph Boland rpbol...@gmail.com wrote:
On Aug 16, 7:29 pm, Ralph Boland rpbol...@gmail.com wrote:
On Aug 14, 1:45 am, richa gupta
I think i hve figured out the actual answer .
Suppose we maintain a queue of N words in the memory.
With two things
1. front 2. rear
As a new word enters (recognized by a space)
- front = front.next;
if(it is already there in the list )
++frequency of occurence;
else{
- temp = rear;
-
@pramod
yeh u r rite..
On Thu, Aug 20, 2009 at 10:20 PM, Pramod Negi negi.1...@gmail.com wrote:
I guess it is famous Younge Tableau Problem of tableau MxN and searching
can be done in O(M+N).
I doubt the problem can be solved in O(lgn) if no space constraint and no
pre-processing
i can improve a bit to
O(n^(log 3 base4 ))
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group,
AFAIK, searching an element in sorted matrix (Young's Tableau) takes O
(n) time.
So I am not sure if O(logn) is actually possible.
_dufus
On Aug 20, 6:41 pm, nagendra kumar nagendra@gmail.com wrote:
How can we find an element in the matrix [n*n] which is sorted row
wise and column wise
10 matches
Mail list logo
