Following approach should work:
1) Count max number of digit in any integer of input. Let it be m. (Thanks
to dave..)
2) For each int having less than m digits:
Convert it to string of length m where you append circularly.
For e.g. if m=5
53 --> 53535
100 --> 10010
34343 --> 34343
8 --> 88888
3) Now lexicographically sort all those strings. Apply same permutations to
first array of integers. (again, thanx to Dave)
4) Concatenate integers of first array.
For e.g.
8 53 147 159 1471470 71
m=7
corresponding string array becomes:
"8888888"
"5353535"
"1471471"
"1591591"
"1471470"
"7171717"
Apply step 3. This gives int array as 8 71 53 15 147 1471470
Thus, solution is 87153151471471470.
Let me know about any counter-examples...
You can apply tricks in programming language that will allow you to save
actually calculating these strings.
For e.g. while comparing two unequal length strings char by char if you find
chars of str1 have exhausted but not of str2, you can set index in str1 to
start of the str1 and continue comparison.
On Sat, Aug 13, 2011 at 2:06 PM, Ashish Sachdeva <ashish.asachd...@gmail.com
> wrote:
> @ $: how ll you manage something like this:
> 2,3,100,90,10
>
> 2nd array becomes: 200,300,100,900,100
> descendng order: 900,300,200,100,100
>
> how to take care which 100 is of 10 cos we need 10 1st...??
> On Aug 13, 1:00 pm, rahul aravind <rahularavin...@gmail.com> wrote:
> > awesome alogoritm dave:):)
> >
> >
> >
> >
> >
> >
> >
> > On Fri, Aug 12, 2011 at 6:48 PM, Dave <dave_and_da...@juno.com> wrote:
> > > @Yasir: I think the following will work. Counterexamples welcome.
> >
> > > Find the number of digits in each of the integers, and find the max of
> > > that number, say m.
> >
> > > Fill a second array as follows: If the ith integer has m digits, copy
> > > it into the second array. If the ith number has less than m digits,
> > > concatenate duplicates of the last digit of the integer to the right
> > > end to expand it to m digits. Examples: m = 3, 7 goes to 777; 82 goes
> > > to 822; 29 goes to 299; 0 goes to 000.
> >
> > > Sort the second array into descending order and carry the first array
> > > along (apply the same permutations to the first array as you do to the
> > > second).
> >
> > > Concatenate the integers in the first array to get the result.
> >
> > > Dave
> >
> > > On Aug 12, 7:34 am, Yasir Imteyaz <yasir....@gmail.com> wrote:
> > > > An array of integers is given and you have to find the largest
> possible
> > > > integer by concatenating all elements:
> >
> > > > example:
> > > > array: 87 36 52
> > > > answer: 875236
> >
> > > > array: 87 9 52
> > > > answer: 98752
> >
> > > --
> > > 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.
>
>
--
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.
