#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%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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
