why will 678 come after 583 ?
okay ., sort from least to most significant digit. append imaginary 0's at
the end of the numbers with varying length to make them of same length....
On Sun, Aug 14, 2011 at 5:54 PM, Puneet Gautam <puneet.nsi...@gmail.com>wrote:
> @ankur: No its not radix sort...radix sort would give wrong answer
> when the input contains heterogeneous numbered digits in the
> array(even when going 4m msd to lsd)...
> eg:
> 32,583,678,1,45,9
>
> Radix sort would give:
> 9,583,678,45,32,1
>
> whereas the answer has to be:
>
> 9,678,543,45,32,1
> and hence largest no created is 967854345321
>
> I think thats the way radix sort will work...
>
> Correct me if i m wrong...!
>
>
> On 8/14/11, Ankur Khurana <ankur.kkhur...@gmail.com> wrote:
> > isn't it a simple question of applying radix sort from most significant
> to
> > least signigicant digit and concatenating all the sorted numbers to get
> the
> > largest number..........
> >
> > On Sat, Aug 13, 2011 at 11:13 PM, Kunal Patil <kp101...@gmail.com>
> wrote:
> >
> >> Let me clarify.
> >>
> >> Lets take example
> >> 53
> >> 147
> >> 1471470
> >>
> >> As per algo:
> >> sort "5353535" , "1471471" and "1471470" lexicographically to get
> answer.
> >> But You are not going to compare all these simultaneously.
> >> Might be you will first compare 53 and 147 for lexicographical order. In
> >> this case you are not required to calculate till max length.
> >> In fact while comparing two strings you will require only till
> (max(len1,
> >> len2)).
> >> (verify it !!)
> >> Comparing 53 and 1471470 doesn't even require till max length.
> >> Comparing 147 and 1471470 (co-incidentally) requires till max length.
> >> (worst case !)
> >>
> >>
> >> Consider you have only 2 strings.
> >> Then above code gives lexicographically largest of these two
> >> (This comparison is considering circular appending).
> >> You can now use this comparator function as parameter for sort()
> function
> >> in c++.
> >> So given set of strings as the input and this comparator function it
> will
> >> sort as per given criteria.
> >>
> >> I mentioned "you have to append circularly till largest of all string
> >> length" only for illustration purpose and to make understanding easier.
> >> Had I mentioned go on comparing each of 2 strings till max(len1,len2),
> It
> >> might not be grasped quickly.
> >> As you can see you will not always require string upto largest length to
> >> determine lexicographical order of 2 strings.
> >>
> >> I am bad at explaining things. So let me know whether this solved your
> >> doubt.
> >>
> >>
> >>
> >> On Sat, Aug 13, 2011 at 10:35 PM, aditi garg
> >> <aditi.garg.6...@gmail.com>wrote:
> >>
> >>> @ kunal : arent we supposed to construct the string fr each number
> equal
> >>> to the max length of any number...
> >>> whr r v doing dat chking in dis algo?
> >>>
> >>>
> >>> On Sat, Aug 13, 2011 at 10:25 PM, Kunal Patil <kp101...@gmail.com>
> wrote:
> >>>
> >>>> I dont know whether this is best approach to do step 2 or not. But
> it's
> >>>> certainly good.
> >>>>
> >>>>
> >>>> //I will show for two strings s1 and s2
> >>>>
> >>>> len1 = s1.length();
> >>>> len2 = s2.length();
> >>>> ind1 = 0; //Index in the first string
> >>>> ind2 = 0; //Index in the second string
> >>>>
> >>>> while( ind1<len1 || ind2 < len2 ) //Match until both strings exhaust
> or
> >>>> function returns
> >>>> {
> >>>> if(ind1 == len1) // String s1 has exhausted, so start over it
> >>>> ind1 = 0;
> >>>>
> >>>> if(ind2 == len2) // String s2 has exhausted, so start over it
> >>>> ind2 = 0;
> >>>>
> >>>> for(; ind1 < len1 && ind2 <len2; ind1++,ind2++ )
> >>>> // Go on comparing until any of the string exhausts or function
> returns
> >>>> {
> >>>> if( s1[ind1] == s2[ind2] ) //Same current char in both string so we
> need
> >>>> to match more char
> >>>> continue;
> >>>> else // mismatch
> >>>> return (s1[ind1] > s2 [ind2] );
> >>>> }
> >>>> }
> >>>>
> >>>> if (ind1==len1 && ind2==len2) // same strings
> >>>> return true;
> >>>>
> >>>> //If I missed anything in the code, let me know
> >>>>
> >>>>
> >>>> On Sat, Aug 13, 2011 at 9:29 PM, aditi garg
> >>>> <aditi.garg.6...@gmail.com>wrote:
> >>>>
> >>>>> @kunal: what is the best way to implement step 2?
> >>>>>
> >>>>>
> >>>>> On Sat, Aug 13, 2011 at 7:33 PM, Ashish Sachdeva <
> >>>>> ashish.asachd...@gmail.com> wrote:
> >>>>>
> >>>>>> @kunal: seems fine.. tried it on some cases...
> >>>>>>
> >>>>>>
> >>>>>> On Sat, Aug 13, 2011 at 5:17 PM, Kunal Patil
> >>>>>> <kp101...@gmail.com>wrote:
> >>>>>>
> >>>>>>> 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.
> >>>>>>>
> >>>>>>
> >>>>>> --
> >>>>>> 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.
> >>>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>>> --
> >>>>> Aditi Garg
> >>>>> Undergraduate Student
> >>>>> Electronics & Communication Divison
> >>>>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
> >>>>> Sector 3, Dwarka
> >>>>> New Delhi
> >>>>>
> >>>>>
> >>>>> --
> >>>>> 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.
> >>>>
> >>>
> >>>
> >>>
> >>> --
> >>> Aditi Garg
> >>> Undergraduate Student
> >>> Electronics & Communication Divison
> >>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
> >>> Sector 3, Dwarka
> >>> New Delhi
> >>>
> >>>
> >>> --
> >>> 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.
> >>
> >
> >
> >
> > --
> > Ankur Khurana
> > Computer Science
> > Netaji Subhas Institute Of Technology
> > Delhi.
> >
> > --
> > 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.
>
>
--
Ankur Khurana
Computer Science
Netaji Subhas Institute Of Technology
Delhi.
--
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.
