[algogeeks] Find an element in sorted matrix
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 algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find an element in sorted matrix
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). --~--~-~--~~~---~--~~ 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, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~--- begin:vcard fn:Anil C R n:C R;Anil email;internet:cr.a...@gmail.com version:2.1 end:vcard
[algogeeks] Re: Find an element in sorted matrix
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 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). --~--~-~--~~~---~--~~ 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, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Check divisibility by 3
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 ??
--
Richa Gupta
(IT-BHU,India)
If the number is an arbitrarily large binary number then
0) Let X be the input number.
1) Add the binary values of each byte of X. Let result be X.
2) If X 255 goto step 1).
3) Look up the answer in a table or
b1) treat X as a base 16 number and add digits. Let the
result be X.
b2) if X 16 go to step b1.
16 should be 15 here. That is: if X 15 go to step b1.
b3) The original number is divisible by 3 IFF X is
divisible by 3 (X in {0,3,6,9,12,15}).
Note that the rule of 3s and the rule of 9s for decimal numbers is be
being
applied here but for the the number 255 and its factors; that is
3, 5, 15, 17, 51, and 85.
It works for the same reason that the rule of 9's (and its factor
rules; i.e.
rule of 3's) works for decimal numbers.
We could call these rules for base 256 numbers
the rule of 3s base 256, the rule of 5's base 256, the rule of 15's
base 256 etc.
The above algorithm can be modified to use 16 bit numbers or 32 bit
numbers instead of bytes.
For 16 bit numbers for the digit base the method can be applied
to factors of 2^16 -1, that is 3,5,17, and 257.
However step 3 cannot be applied to 17 or 257.
For 32 bit numbers you have the additional factor 2^16 + 1 (and the
numbers in its prime factorization but unfortunately 2^ 16 + 1 is
prime).
It can also be modified to determine if the input number is divisible
by 5,6,7,9,12, 14, or 15.
To do digits 7 or 9 one has to use base 64 digits instead of base
256.
(7 * 9 = 63 = 64 - 1).
I believe divisibility by 13 can also be done but a different
algorithm is needed.
Ralph Boland
Ralph Boland
--~--~-~--~~~---~--~~
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, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Find an element in sorted matrix
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 .. left alone is B C D we can now search recursively.. t(n)= 3 (t/4)+ constant t(n)= O(n^(log 3 base 4)) which is better than linear.. --~--~-~--~~~---~--~~ 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, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Check divisibility by 3
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 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 ??
--
Richa Gupta
(IT-BHU,India)
If the number is an arbitrarily large binary number then
0) Let X be the input number.
1) Add the binary values of each byte of X. Let result be X.
2) If X 255 goto step 1).
3) Look up the answer in a table or
b1) treat X as a base 16 number and add digits. Let the
result be X.
b2) if X 16 go to step b1.
16 should be 15 here. That is: if X 15 go to step b1.
b3) The original number is divisible by 3 IFF X is
divisible by 3 (X in {0,3,6,9,12,15}).
Note that the rule of 3s and the rule of 9s for decimal numbers is be
being
applied here but for the the number 255 and its factors; that is
3, 5, 15, 17, 51, and 85.
It works for the same reason that the rule of 9's (and its factor
rules; i.e.
rule of 3's) works for decimal numbers.
We could call these rules for base 256 numbers
the rule of 3s base 256, the rule of 5's base 256, the rule of 15's
base 256 etc.
The above algorithm can be modified to use 16 bit numbers or 32 bit
numbers instead of bytes.
For 16 bit numbers for the digit base the method can be applied
to factors of 2^16 -1, that is 3,5,17, and 257.
However step 3 cannot be applied to 17 or 257.
For 32 bit numbers you have the additional factor 2^16 + 1 (and the
numbers in its prime factorization but unfortunately 2^ 16 + 1 is
prime).
It can also be modified to determine if the input number is divisible
by 5,6,7,9,12, 14, or 15.
To do digits 7 or 9 one has to use base 64 digits instead of base
256.
(7 * 9 = 63 = 64 - 1).
I believe divisibility by 13 can also be done but a different
algorithm is needed.
Ralph Boland
Ralph Boland
--~--~-~--~~~---~--~~
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, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Question asked in MS interview
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;
- rear = newWord;
- temp.next = rear;
(simple insertion at the rear end of queue)
}
I think this will work ..
if Anyone thinks it won't then Do suggest modification or indicate
error
Pawandeep
--~--~-~--~~~---~--~~
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, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Find an element in sorted matrix
@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 constraint present. On Thu, Aug 20, 2009 at 9:42 PM, Anil C R cr.a...@gmail.com wrote: 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). --~--~-~--~~~---~--~~ 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, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find an element in sorted matrix
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, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find an element in sorted matrix
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 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
