@abc- i'm afraid u wont find this level of participation if that were the case... ppl post the solution they think works...
On Feb 1, 12:06 am, abc abc <may.i.answ...@gmail.com> wrote: > Guys please check correctness of your algorithm before posting > > On Mon, Jan 31, 2011 at 11:47 PM, ritu <ritugarg.c...@gmail.com> wrote: > > @Ralph > > "Build a data structure on array B[1..n] in O(n) time such that > > > the following problem can be solved in O(log n) time: > > > Given an index i and value v, find the index j of the first > > > element in B such that j >= i and B[j] > v. > > > Return -1 if no such j exists. > > > " > > > then it ll take n*lg(n) time ... while a o(n) solution exists > > > On Jan 31, 9:25 pm, Ralph Boland <rpbol...@gmail.com> wrote: > > > On Jan 30, 11:00 pm, ritu <ritugarg.c...@gmail.com> wrote: > > > > > You are given an array (unsorted) and for every element i, find the > > > > first occurance of an element j (in the remaining array) that is > > > > greater than or equal to i. If no such j occurs then print -1. > > > > Eg: Input---> A={1,3,5,7,6,4,8} > > > > Output---> 3 5 7 8 8 8 -1 > > > > Time Complexity:O(n) > > > > Space Complexity:O(n) > > > > I solved a version of this problem in my thesis. > > > > Build a data structure on array B[1..n] in O(n) time such that > > > the following problem can be solved in O(log n) time: > > > Given an index i and value v, find the index j of the first > > > element in B such that j >= i and B[j] > v. > > > Return -1 if no such j exists. > > > > I have an application of this data structure in my thesis (which > > > is why I invented it) but I would love to hear other applications. > > > > 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<algogeeks%2bunsubscr...@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 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?hl=en.