@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.
