Re: [algogeeks] search a 2d sorted array in less than O(n)
Thanks for pointing out. I was wrong because I assumed that numbers would be in continuous increasing order when numbers in each row are written in a line taking each row at a time. On Mon, Sep 27, 2010 at 5:49 PM, Nikhil Jindal wrote: > @saurabh.nsit: > > Consider the following array: > > 1 2 6 7 > 2 3 7 8 > 4 5 8 9 > 5 7 9 10 > > And the item to be searched is 6. As I understand it, using your approach > you will search 6 in only the second and third row, which will not give the > correct solution. > Hope this clears a few doubts. > > @Gene: > Analysing the complexity of ur algo: > > T(n) = 3*T(n/2) + O(1) > > which is n^(log_2(3)) = n^1.6. > > Cheers > Nikhil Jindal > > On Sun, Sep 26, 2010 at 11:14 PM, saurabh singh wrote: > >> As you mentioned ultimately element to be searched should either be in row >> 'i' (ahead of [i,i] element) or in row i+1 (before [i+1,i+1] element). Since >> each row contain numbers in sorted order so u can do binary search on these >> two rows and ultimately the complexity will be O(logn) only >> >> On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal >> wrote: >> >>> >>> >>> On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh >>> wrote: >>> solution 1: use concept of quad-tree and do binary search in that tree solution 2: do binary search on major diagonal. ultimately u will narrow down to search for element in 2 rows. in these two rows again do binary search. >>> >>> How do you narrow down to two rows? Please explain. >>> By searching on the diagonal, you get two elements such that one is >>> lesser than the number being searched for and the next is greater. let them >>> be i,i, and i+1,i+1. >>> >>> So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But >>> the number could be anywhere in the rest of the array >>> >>> any solution will lead you to O(log(n)) time On Tue, Sep 21, 2010 at 5:10 PM, jagadish wrote: > Hi all, > Given a 2d array which is sorted row wise and column wise as well, > find a specific element in it in LESS THAN O(n). > PS: an O(n) solution would involve skipping a column or a row each > time from the search and moving accordingly. > Solution less than O(n) is desirable! > > -- > You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. > To post to this group, send email to algoge...@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?hl=en. > > -- Thanks & Regards, Saurabh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en. >>> >>> Please access the attached hyperlink for an important electronic >>> communications disclaimer: >>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php >>> >>> >>> >>> -- >>> >>> >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> >>> To post to this group, send email to algoge...@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?hl=en. >>> >>> >>> >> >> >> -- >> Thanks & Regards, >> Saurabh >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@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?hl=en. >> > > Please access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@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?hl=en. > > > -- Thanks & Regards, Saurabh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit t
[algogeeks] Re: sum of primes
Twin primes are a pair of prime numbers that differ by 2. Dave On Sep 27, 11:26 am, radha krishnan wrote: > These are called Twin Primes ...:))) > > On Thu, Sep 23, 2010 at 11:29 PM, Rishi Agrawal > > > > wrote: > > Apart from 1, 2 and 3, all the prime numbers are either of the form (6*n - > > 1) or (6*n + 1). > > > Can we use this property to generate the primes till we get 1 primes. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@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?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: search a 2d sorted array in less than O(n)
Well, friend, we're both wrong. The algorithm will find 6 just fine. It will choose 3 as the middle element. Since 6 is bigger, it will throw away the subarray 1 2 2 3 and check the other 3 subarrays. When it checks 6 7 7 8 It will find the 6 on the first try. I just verified this by running the code. Second, I should have solved the recurrence. You're right that it's ~ n^1.6 . Throwing away a quarter of the _elements_ isn't good enough because that number is n^2. The algorithm is only sublinear in the number of elements, which of course is worse than the standard algorithm that starts at the lower left corner and steps along a jagged path of max length ~2n. But I should have seen that you can split the L-shaped remaining piece of each subarray into only TWO pieces rather than 3. So the recursive calls should have been: return (x < a[mi][mj]) ? search(a, x, i0, mi - 1, j0, j1, i, j) || search(a, x, mi, i1, j0, mj - 1, i, j) : search(a, x, i0, mi, mj + 1, j1, i, j) || search(a, x, mi + 1, i1, j0, j1, i, j); With this change the recurrence is more complicated, but it should be faster than n^1.6 . I'm not going to try it tonight... On Sep 27, 8:19 am, Nikhil Jindal wrote: > @saurabh.nsit: > > Consider the following array: > > 1 2 6 7 > 2 3 7 8 > 4 5 8 9 > 5 7 9 10 > > And the item to be searched is 6. As I understand it, using your approach > you will search 6 in only the second and third row, which will not give the > correct solution. > Hope this clears a few doubts. > > @Gene: > Analysing the complexity of ur algo: > > T(n) = 3*T(n/2) + O(1) > > which is n^(log_2(3)) = n^1.6. > > Cheers > Nikhil Jindal > > On Sun, Sep 26, 2010 at 11:14 PM, saurabh singh wrote: > > > > > > > As you mentioned ultimately element to be searched should either be in row > > 'i' (ahead of [i,i] element) or in row i+1 (before [i+1,i+1] element). Since > > each row contain numbers in sorted order so u can do binary search on these > > two rows and ultimately the complexity will be O(logn) only > > > On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal > > wrote: > > >> On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh > >> wrote: > > >>> solution 1: > >>> use concept of quad-tree and do binary search in that tree > > >>> solution 2: > >>> do binary search on major diagonal. ultimately u will narrow down to > >>> search for element in 2 rows. in these two rows again do binary search. > > >> How do you narrow down to two rows? Please explain. > >> By searching on the diagonal, you get two elements such that one is lesser > >> than the number being searched for and the next is greater. let them be > >> i,i, > >> and i+1,i+1. > > >> So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But > >> the number could be anywhere in the rest of the array > > >>> any solution will lead you to O(log(n)) time > > >>> On Tue, Sep 21, 2010 at 5:10 PM, jagadish wrote: > > Hi all, > Given a 2d array which is sorted row wise and column wise as well, > find a specific element in it in LESS THAN O(n). > PS: an O(n) solution would involve skipping a column or a row each > time from the search and moving accordingly. > Solution less than O(n) is desirable! > > -- > You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com .com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > >>> -- > >>> Thanks & Regards, > >>> Saurabh > > >>> -- > >>> You received this message because you are subscribed to the Google Groups > >>> "Algorithm Geeks" group. > >>> To post to this group, send email to algoge...@googlegroups.com. > >>> To unsubscribe from this group, send email to > >>> algogeeks+unsubscr...@googlegroups.com >>> .com> > >>> . > >>> For more options, visit this group at > >>>http://groups.google.com/group/algogeeks?hl=en. > > >> Please access the attached hyperlink for an important electronic > >> communications > >> disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > >> -- > > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > > >> To post to this group, send email to algoge...@googlegroups.com. > > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com > >> . > > >> For more options, visit this group > >> athttp://groups.google.com/group/algogeeks?hl=en. > > > -- > > Thanks & Regards, > > Saurabh > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr.
Re: [algogeeks] finding largest and second largest elements
hey isn't it suppposed to be tournament problem.. On Fri, Sep 24, 2010 at 12:06 AM, Divesh Dixit < dixit.coolfrog.div...@gmail.com> wrote: > finding largest and second largest elements from a set of n elements > by means of > Minimum comparison of n+celling(log n) +2 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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?hl=en. > > -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] Finding hash collisions without storage
u can use log(n)+1 space to do that by using bit string On Mon, Sep 27, 2010 at 10:37 PM, AdrianW wrote: > Suppose you have N strings that can be generated on-the-fly, and you > wanted to discover if a hash function generates any collisions. Is > there a way to do this without O(N) storage? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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?hl=en. > > -- Thanks & Regards, Saurabh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Finding hash collisions without storage
Suppose you have N strings that can be generated on-the-fly, and you wanted to discover if a hash function generates any collisions. Is there a way to do this without O(N) storage? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: arrays
Move-To-The-Front. On Sep 27, 11:58 pm, Anand wrote: > Given an array of integers, for each index i, you have to swap the value at > i with the first value smaller than A[ i ] that comes after index i -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] arrays
Given an array of integers, for each index i, you have to swap the value at i with the first value smaller than A[ i ] that comes after index i -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: Amazon Interview
it's a compression problem. using hex instead of oct saves more space 00aaa0ss yyy => 50 2a 0 1s 3f 1\s ay On Sep 15, 8:21 am, bittu wrote: > A file is given with many 0s stored in continuous way , store it in > another file such that when you store try saving the space by using > minimum amount of space. When you want to create the original file , > you should be able to do so with the new file created -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: ReVerse a string using recursion
any type of replace would need at least one extra memory space.
recursion is the worst, depends how you implement recursion. one
iteration might depends on another, which depends one other, and so
on.. each iteration hold its own "stack"
On Sep 23, 1:59 pm, Albert wrote:
> How to reverse a String using recursion in C without using any extra
> memory?
>
> the question seems to be simple.
>
> char* strrev(char *)
> {
> ...
> ...
> ...
>
> }
>
> Try to give all the answers for this prototype.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Iterative Quick sort
Hi can any one suggest an efficient algorithm for iterative quick sort Thanks in advance. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] Re: sum of primes
These are called Twin Primes ...:))) On Thu, Sep 23, 2010 at 11:29 PM, Rishi Agrawal wrote: > Apart from 1, 2 and 3, all the prime numbers are either of the form (6*n - > 1) or (6*n + 1). > > Can we use this property to generate the primes till we get 1 primes. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: sum of primes
@Sourav: What you are missing is that the algorithm is a manual one that will answer the question asked in a few moments without writing any computer code. Looking in the first file, you find that there are 1229 prime numbers less than 10,000. Looking in the second file, you find that the sum of the first 1229 prime numbers is 5,736,396. It all takes less than a minute. Why do you need code when you can answer the question so simply without it? Dave On Sep 27, 6:54 am, sourav wrote: > @Dave > > I cannot see any code at the links you have provided. I only see the > prime numbers. am I missing something here..? > > Thanks, > Sourav > > On Sep 23, 10:59 pm, Rishi Agrawal wrote: > > > > > Apart from 1, 2 and 3, all the prime numbers are either of the form (6*n - > > 1) or (6*n + 1). > > > Can we use this property to generate the primes till we get 1 primes.- > > Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] Re: BST in BT
@Prodigy As per your example, 8 15 20 25 which is the is indeed the maximum binary search tree in this binary tree is only a solution to smaller problem used to solve a bigger problem. The solution to smaller problem can be translated directly to the solution of the bigger problem. On Mon, Sep 27, 2010 at 8:28 AM, prodigy <1abhishekshu...@gmail.com> wrote: > 15 > /\ > 8 25 > /\ > 20 22 > > > On Sep 26, 10:45 am, Chonku wrote: > > This can also be done if we do an inorder traversal of the binary tree > and > > look for the longest continuous sequence of numbers in ascending order. > > Your idea will fail for above case. > > In Order => 8 15 20 25 22 > longest continuous sequence of numbers in ascending order => 8 15 20 > 25 > > But that's not the answer (I hope you realize what correct output > would be ) > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: BST in BT
For solution to this problem see
http://groups.google.co.in/group/algogeeks/browse_thread/thread/adc95dcf96020a7/2943fd3c5a116fee?hl=en&lnk=gst&q=binary+tree+to+binary+serach+tree#
In that thread, I have a doubt regarding solution posted by @"Algoose
Chase". The code posted is good as I feel except for the condition
if( NodeL->Data > root->data)
{
}
if( NodeR->Data <= root->data)
{
}
Here If you find that the present node's (say 'n1') value if less than
the MAX (say 'n2' ) of so far constructed BST in the left tree, then
if is for sure that that MAX ('n2') of the left tree will replace the
present node 'n1'. This will make sure that all nodes to the left are
less than the new root 'n2', but we are not sure that the remaining
nodes n the left tree are all less than 'n1'.
So in "if( NodeL->Data > root->data)" condition, "temp = root-data;
root->data = NodeL->data" is correct but instead of doing
Nodel->data = root->data;
BinarytoBST(NodeL)
we should simply say
deleteNode(tree->left,NodeL);//This will delete NodeL from a BST
rooted at tree->left, taking into account delete conditions for
deleting right most child of BST //(because NodeL was the
right most child)
InsertNode(tree->left,temp);
Do share your views.
Thanks,
Sourav
On Sep 27, 7:58 am, prodigy <1abhishekshu...@gmail.com> wrote:
> 15
> / \
> 8 25
> / \
> 20 22
>
> On Sep 26, 10:45 am, Chonku wrote:
>
> > This can also be done if we do an inorder traversal of the binary tree and
> > look for the longest continuous sequence of numbers in ascending order.
>
> Your idea will fail for above case.
>
> In Order => 8 15 20 25 22
> longest continuous sequence of numbers in ascending order => 8 15 20
> 25
>
> But that's not the answer (I hope you realize what correct output
> would be )
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: finding largest and second largest elements
Very Nice Simple approach @Dave On Sep 24, 12:56 am, Dave wrote: > Do a single-elimination tournament of the numbers, where the larger > wins each "game". This will take n/2 + n/4 + ... + 1 <= n-1 > comparisons. The second largest will be among the numbers that lost to > the largest in one of the "games". As you conduct the tournament, keep > track of the losers. Since there will be at most ceiling(log_2(n)) > stages in the tournament, you can find the largest of the losers to > the winner in ceiling(log_2(n))-1 comparisons. > > Dave > > On Sep 23, 1:36 pm, Divesh Dixit > wrote: > > > finding largest and second largest elements from a set of n elements > > by means of > > Minimum comparison of n+celling(log n) +2 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: sum of primes
@Dave I cannot see any code at the links you have provided. I only see the prime numbers. am I missing something here..? Thanks, Sourav On Sep 23, 10:59 pm, Rishi Agrawal wrote: > Apart from 1, 2 and 3, all the prime numbers are either of the form (6*n - > 1) or (6*n + 1). > > Can we use this property to generate the primes till we get 1 primes. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] search a 2d sorted array in less than O(n)
@saurabh.nsit: Consider the following array: 1 2 6 7 2 3 7 8 4 5 8 9 5 7 9 10 And the item to be searched is 6. As I understand it, using your approach you will search 6 in only the second and third row, which will not give the correct solution. Hope this clears a few doubts. @Gene: Analysing the complexity of ur algo: T(n) = 3*T(n/2) + O(1) which is n^(log_2(3)) = n^1.6. Cheers Nikhil Jindal On Sun, Sep 26, 2010 at 11:14 PM, saurabh singh wrote: > As you mentioned ultimately element to be searched should either be in row > 'i' (ahead of [i,i] element) or in row i+1 (before [i+1,i+1] element). Since > each row contain numbers in sorted order so u can do binary search on these > two rows and ultimately the complexity will be O(logn) only > > On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal wrote: > >> >> >> On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh >> wrote: >> >>> solution 1: >>> use concept of quad-tree and do binary search in that tree >>> >>> solution 2: >>> do binary search on major diagonal. ultimately u will narrow down to >>> search for element in 2 rows. in these two rows again do binary search. >>> >> >> How do you narrow down to two rows? Please explain. >> By searching on the diagonal, you get two elements such that one is lesser >> than the number being searched for and the next is greater. let them be i,i, >> and i+1,i+1. >> >> So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But >> the number could be anywhere in the rest of the array >> >> >>> >>> any solution will lead you to O(log(n)) time >>> >>> >>> On Tue, Sep 21, 2010 at 5:10 PM, jagadish wrote: >>> Hi all, Given a 2d array which is sorted row wise and column wise as well, find a specific element in it in LESS THAN O(n). PS: an O(n) solution would involve skipping a column or a row each time from the search and moving accordingly. Solution less than O(n) is desirable! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en. >>> >>> >>> -- >>> Thanks & Regards, >>> Saurabh >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@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?hl=en. >>> >> >> Please access the attached hyperlink for an important electronic >> communications disclaimer: >> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php >> >> >> >> -- >> >> >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> >> To post to this group, send email to algoge...@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?hl=en. >> >> >> > > > -- > Thanks & Regards, > Saurabh > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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?hl=en. > Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: search a 2d sorted array in less than O(n)
I feel the binary search approach as given by Saurabh Singh or like
"moving from top right row, doing binary search in the row 0, find the
element being searched (say x) or one less than that (say y), followed
by binary search in the column below 'y' and proceeding in this way"
can give a less than O(n) solution.
Please provide your comments in any
Thanks
Sourav
On Sep 27, 11:09 am, prodigy <1abhishekshu...@gmail.com> wrote:
> Actual complexity of above algorithm = O(n^1.6)
>
> On Sep 27, 8:19 am, Gene wrote:
>
> > If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
> > the middle. There are now 3 possibilities:
>
> > 1) The middle element is the one you're looking for, so you're done.
> > 2) The element you're looking for is smaller. In this case you can
> > throw out about 1/4 of the array: everything right and downward from
> > a[m/2][n/2] (including row m/2 and column n/2) because these elements
> > are all larger than the middle one.
> > 3) The element you're looking for is larger. In this case you can
> > again throw out about 1/4 of the array: everything left and upward
> > from a[m/2][n/2] inclusive.
>
> > Then you can search the remaining 3/4 of the array recursively.
>
> > By throwing away 1/4 of mn elements at each step, you can easily work
> > out the recurrence to see you'll get O(log mn) = O(log(max(m, n)))
> > performance.
>
> > Here is code and a very quick unit test:
>
> > #include
> > #include
>
> > typedef int SORTED_ARRAY[100][100];
>
> > /* Look for x in row- and column-sorted a[i0..i1][j0..j1].
> > Put indices in *i and *j and return 1 if found,
> > else return 0.
> > */
> > int search(SORTED_ARRAY a, int x,
> > int i0, int i1,
> > int j0, int j1,
> > int *i, int *j)
> > {
> > if (i0 <= i1 && j0 <= j1) {
> > int mi = (i0 + i1) / 2;
> > int mj = (j0 + j1) / 2;
> > if (x == a[mi][mj]) {
> > *i = mi; *j = mj;
> > return 1;
> > }
> > return (x < a[mi][mj]) ?
> > search(a, x, i0, mi - 1, j0, mj - 1, i, j) ||
> > search(a, x, i0, mi - 1, mj, j1, i, j) ||
> > search(a, x, mi, i1, j0, mj - 1, i, j)
> > :
> > search(a, x, mi + 1, i1, mj + 1, j1, i, j) ||
> > search(a, x, i0, mi, mj + 1, j1, i, j) ||
> > search(a, x, mi + 1, i1, j0, mj, i, j);
> > }
> > return 0;
>
> > }
>
> > int max(int x, int y) { return x > y ? x : y; }
>
> > int main(void)
> > {
> > int i, j, m, n, ri, rj;
> > SORTED_ARRAY a;
>
> > // A small unit test. Build a m x n
> > // sorted array with random differences.
> > m = 100; n = 100;
> > a[0][0] = 0;
> > for (i = 1; i < m; i++)
> > a[i][0] = a[i - 1][0] + rand() % 1000;
> > for (j = 1; j < n; j++) {
> > a[0][j] = a[0][j - 1] + rand() % 1000;
> > for (i = 1; i < m; i++)
> > a[i][j] = max(a[i - 1][j], a[i][j - 1]) + rand() % 1000;
> > }
> > for (i = 0; i < m; i++) {
> > for (j = 0; j < n; j++) {
> > printf("%8d", a[i][j]);
> > }
> > printf("\n");
> > }
> > for (i = 0; i < m; i++) {
> > for (j = 32; j < n; j++) {
> > int r = search(a, a[i][j], 0, m - 1, 0, n - 1, &ri, &rj);
> > if (!r) {
> > printf("failed at a[%d][%d]\n", i, j, a[i][j]);
> > return 1;
> > }
> > else if (a[ri][rj] != a[i][j]) {
> > printf("mistake at a[%d][%d]=%d: found a[%d][%d]=%d\n",
> > i, j, a[i][j], ri, rj, a[ri][rj]);
> > return 1;
> > }
> > }
> > }
> > printf("pass!\n");
>
> > return 0;
>
> > }
>
> > On Sep 21, 7:40 am, jagadish wrote:
>
> > > Hi all,
> > > Given a 2d array which is sorted row wise and column wise as well,
> > > find a specific element in it in LESS THAN O(n).
> > > PS: an O(n) solution would involve skipping a column or a row each
> > > time from the search and moving accordingly.
> > > Solution less than O(n) is desirable!
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] Re: next multiple of 8
Please correct. ans = (x|7)+1. Thanks Dave. On Mon, Sep 27, 2010 at 5:42 PM, saurabh agrawal wrote: > This problem is already solved. > ans=(x|1)+1 > > > On Mon, Sep 27, 2010 at 5:15 PM, nishaanth wrote: > >> try x+8-(x&7 ) >> >> On Sep 26, 4:47 am, Dave wrote: >> > @Shrevan: I mistyped what I intended. Try answer = (x | 7) + 1; >> > >> > Dave >> > >> > On Sep 26, 5:51 am, Shravan wrote: >> > >> > > @Dave >> > > Your answer will be always 2 irrespective of the value of 'x'. >> > > BTW I too didn't the question. >> > >> > > On Sep 26, 2:42 pm, Mahendran MaheM wrote: >> > >> > > > sry...i dnt get the qstn clearly. >> > >> > > > On Sat, Sep 25, 2010 at 10:18 PM, Dave >> wrote: >> > > > > Simpler: answer = (x || 7) + 1 >> > >> > > > > Dave >> > >> > > > > On Sep 25, 10:14 am, rajess wrote: >> > > > > > scan last(left) 4 bits .if the bits are not 1000.make them >> 1000.else >> > > > > > scan from left till u find first one(1).make this bit 1.and make >> > > > > > last(left) bits as 1000 >> > >> > > > > -- >> > > > > You received this message because you are subscribed to the Google >> Groups >> > > > > "Algorithm Geeks" group. >> > > > > To post to this group, send email to algoge...@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?hl=en. >> > >> > > > -- >> > > > MAHEM- Hide quoted text - >> > >> > > - Show quoted text - >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@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?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] Re: next multiple of 8
This problem is already solved. ans=(x|1)+1 On Mon, Sep 27, 2010 at 5:15 PM, nishaanth wrote: > try x+8-(x&7 ) > > On Sep 26, 4:47 am, Dave wrote: > > @Shrevan: I mistyped what I intended. Try answer = (x | 7) + 1; > > > > Dave > > > > On Sep 26, 5:51 am, Shravan wrote: > > > > > @Dave > > > Your answer will be always 2 irrespective of the value of 'x'. > > > BTW I too didn't the question. > > > > > On Sep 26, 2:42 pm, Mahendran MaheM wrote: > > > > > > sry...i dnt get the qstn clearly. > > > > > > On Sat, Sep 25, 2010 at 10:18 PM, Dave > wrote: > > > > > Simpler: answer = (x || 7) + 1 > > > > > > > Dave > > > > > > > On Sep 25, 10:14 am, rajess wrote: > > > > > > scan last(left) 4 bits .if the bits are not 1000.make them > 1000.else > > > > > > scan from left till u find first one(1).make this bit 1.and make > > > > > > last(left) bits as 1000 > > > > > > > -- > > > > > You received this message because you are subscribed to the Google > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to algoge...@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?hl=en. > > > > > > -- > > > > MAHEM- Hide quoted text - > > > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] Re: Bitwise operator - Adobe
#include
using namespace std;
int main()
{
int n,temp,ans=1;
cin >> n;
temp=n/8;
temp++;
cout << "hi" << temp<<"\n";
while(temp--)
{
temp=temp<<3;
}
cout << temp;
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: next multiple of 8
try x+8-(x&7 ) On Sep 26, 4:47 am, Dave wrote: > @Shrevan: I mistyped what I intended. Try answer = (x | 7) + 1; > > Dave > > On Sep 26, 5:51 am, Shravan wrote: > > > @Dave > > Your answer will be always 2 irrespective of the value of 'x'. > > BTW I too didn't the question. > > > On Sep 26, 2:42 pm, Mahendran MaheM wrote: > > > > sry...i dnt get the qstn clearly. > > > > On Sat, Sep 25, 2010 at 10:18 PM, Dave wrote: > > > > Simpler: answer = (x || 7) + 1 > > > > > Dave > > > > > On Sep 25, 10:14 am, rajess wrote: > > > > > scan last(left) 4 bits .if the bits are not 1000.make them 1000.else > > > > > scan from left till u find first one(1).make this bit 1.and make > > > > > last(left) bits as 1000 > > > > > -- > > > > You received this message because you are subscribed to the Google > > > > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to algoge...@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com > > > .com> > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > > MAHEM- Hide quoted text - > > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] Re: do this: two numbers with min diff
If their is no constrain on assumptions.
1.Sort the array.
2. check the dif between 2 elements.
{ 99,35,45,33,88,9098,112,33455,678,3}
sorted arrary : { } would be something.
now update the min_diff.
another example : { 7,8,1,3,5,4}
sorted arrary : { 1,3,4,5,7,8}
min diff is 1.
Please correct me if i missed something.
On Mon, Sep 27, 2010 at 1:13 PM, satish wrote:
> step1>construct heap using siftdown. // time complexity wil be O(n) and
> space complexity O(1).
> step2>take mindifference=a[1].
> step3>for i=1 ,i<=n/2 do
> { find the difference of (root,root-left),(root,root->right)and
> (root->left,root->right).and maintain mindifference is the smallest
> difference of among
>three differences.
> }
> step4>return mindifference.
>
>
> plz correct me if im wrong
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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?hl=en.
Re: [algogeeks] Re: do this: two numbers with min diff
step1>construct heap using siftdown. // time complexity wil be O(n) and
space complexity O(1).
step2>take mindifference=a[1].
step3>for i=1 ,i<=n/2 do
{ find the difference of (root,root-left),(root,root->right)and
(root->left,root->right).and maintain mindifference is the smallest
difference of among
three differences.
}
step4>return mindifference.
plz correct me if im wrong
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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?hl=en.
