we can create a height balanced tree with all nodes having their value and also their index value.. can be done in o(n) then we need to look to d right side of the node and check for index(greater ).. which will be o(log(n)) correct me if i m wrong..
On Tue, Feb 1, 2011 at 7:50 PM, Aman Goyal <[email protected]> wrote: > this code will work only for this test case, it is wrong for all > cases...eg 3 4 9 8 6 7 10 > there will be -1 output for 8 and 9 which is actually wrong.. > > > On Tue, Feb 1, 2011 at 6:01 PM, Veenus Gupta <[email protected]>wrote: > >> #define N 7 >> int main() >> >> { >> int a[N]={1,3,5,7,6,4,8}; >> int m[N]; >> m[N-1]=-1; >> for(int i=N-2;i>=0;i--) >> { >> if(a[i]<=a[i+1]) >> m[i]=a[i+1]; >> else >> m[i]=m[i+1]; >> } >> for(int i=0;i<N;i++) >> cout<<m[i]<<"\t"; >> system("pause"); >> } >> >> On Feb 1, 1:06 pm, abc abc <[email protected]> wrote: >> > Guys please check correctness of your algorithm before posting >> > >> > >> > >> > >> > >> > >> > >> > On Mon, Jan 31, 2011 at 11:47 PM, ritu <[email protected]> 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 <[email protected]> wrote: >> > > > On Jan 30, 11:00 pm, ritu <[email protected]> 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 [email protected]. >> > > To unsubscribe from this group, send email to >> > > [email protected]<algogeeks%[email protected]> >> <algogeeks%2Bunsubscribe@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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
