@ Lucifer :
so i guess this is what you are trying to say:-
input : 2 3 5 78
L(0)= {2)
L(1)= {2,3} , {3,2} --------> {3,2} is greatest
L(2)= {3,2,5} , { 3,5,2 } , {5,3,2 } ----> {5,3,2} is the greatest
L(3)= {5,3,2,78} , {5,3,78,2} , {5,78,3,2 } , {78,5,3,2}
{78,5,3,2} ----> found
nice :)
On Wed, Dec 14, 2011 at 6:32 PM, Lucifer <sourabhd2...@gmail.com> wrote:
> @dipit
>
> Its not really a strict comparison..
>
> To sort all we are doing is, keeping in mind that all the elements are
> integers, is as follows:
>
> Say, we need to sort two elements.. A and B
>
> i = no. of digits in A, i.e Log10 (A)
> j = no. of digits in B, i.e Log10 (B)
>
> k = min (i, j);
>
> x1 = A / pow(10, i - k);
> x2 = B / pow(10, i - k);
>
> Now do a normal compare and sort based on max(x1, x2)
>
> In case, x1 == x2, say, j (B) is greater than i (A)..
>
> Then take the second half of B , and using the above approach cited..
> use the algo given above for the special case...
>
> Yes, its not a straightforward integral comparison... but then its not
> a string comparison as well... If thats whats you were pointing
> at....
>
> On Dec 14, 5:51 pm, Lucifer <sourabhd2...@gmail.com> wrote:
> > @atul anand
> >
> > I am guessing that you referring to the the n^2 solution.. if yes,
> > then no i am not considering all permutations...
> > Basically L(i) is the reordering of A[i] which depicts the largest no.
> > that can be formed when read from left to right i.e MSD to LSD...
> >
> > Hence, L(i+1) can be found by placing A[i+1] in the correct position
> > within array A[0, i+1] so to make it as the largest integer..
> >
> > For ex -
> >
> > Say the given input is {a, b, c, d}
> >
> > Now L(3) is say, {c, a, b}
> >
> > Hence, L(4) will be finding which one of the following is the
> > greatest..
> > { c, a, b, d} , { c, a, d, b}, { c, d, a, b} , { d, c, a, b}...
> >
> > Basically the above approach is dynamic approach.. resulting in time
> > complexity ( 2+ 3 + 4 + ... n+1) = O(n^2) for n given integers...
> >
> > On Dec 13, 11:07 am, Dipit Grover <dipitgro...@gmail.com> wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @Lucifer (Regarding your latest approach) - I guess you meant string
> based
> > > comparison sort in the first step, as in 9 would be greater than 10.
> The
> > > special case seems correct but I doubt the complexity being nlog n,
> > > considering the special case.
>
> --
> 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.
>
>
--
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.
