What about the case 1, 90 ? It will give 190 as the answer, isn't it? Or am I getting your algo wrong?
On Sun, Aug 14, 2011 at 11:56 PM, Dipankar Patro <[email protected]>wrote: > Ankur, I agree with your algo. > > -> radix sort from least significant to most significant. > -> a slight modification can be done on the appending 0 part. > when you find the a digit is absent from the number, you leave the number. > e.g > 95, 87, 9, 45, 38 > > one's place, sort: (descending) > 9, 38, 87, 95, 45 > > ten's place sort: (leave the number at its place if it doesn't have a ten's > place) > 9, 95, 87, 45, 38 > > ^^ I think this will work for all cases. Will require extremely good use of > pointers. > > On 14 August 2011 19:16, Ankur Khurana <[email protected]> wrote: > >> 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 >> <[email protected]>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 <[email protected]> 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 <[email protected]> >>> 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 >>> >> <[email protected]>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 <[email protected]> >>> 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 >>> >>>> <[email protected]>wrote: >>> >>>> >>> >>>>> @kunal: what is the best way to implement step 2? >>> >>>>> >>> >>>>> >>> >>>>> On Sat, Aug 13, 2011 at 7:33 PM, Ashish Sachdeva < >>> >>>>> [email protected]> wrote: >>> >>>>> >>> >>>>>> @kunal: seems fine.. tried it on some cases... >>> >>>>>> >>> >>>>>> >>> >>>>>> On Sat, Aug 13, 2011 at 5:17 PM, Kunal Patil >>> >>>>>> <[email protected]>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 < >>> >>>>>>> [email protected]> 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 <[email protected]> >>> wrote: >>> >>>>>>>> > awesome alogoritm dave:):) >>> >>>>>>>> > >>> >>>>>>>> > >>> >>>>>>>> > >>> >>>>>>>> > >>> >>>>>>>> > >>> >>>>>>>> > >>> >>>>>>>> > >>> >>>>>>>> > On Fri, Aug 12, 2011 at 6:48 PM, Dave < >>> [email protected]> >>> >>>>>>>> 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 <[email protected]> >>> 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 >>> [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. >>> >>>>>>>> >>> >>>>>>>> -- >>> >>>>>>>> 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. >>> >>>>>>>> >>> >>>>>>>> >>> >>>>>>> -- >>> >>>>>>> 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. >>> >>>>>>> >>> >>>>>> >>> >>>>>> -- >>> >>>>>> 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. >>> >>>>>> >>> >>>>> >>> >>>>> >>> >>>>> >>> >>>>> -- >>> >>>>> 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 [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. >>> >>>>> >>> >>>> >>> >>>> -- >>> >>>> 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. >>> >>>> >>> >>> >>> >>> >>> >>> >>> >>> -- >>> >>> 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 [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. >>> >>> >>> >> >>> >> -- >>> >> 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. >>> >> >>> > >>> > >>> > >>> > -- >>> > 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 [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. >>> > >>> > >>> >>> -- >>> 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. >>> >>> >> >> >> -- >> 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 [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. >> > > > > -- > > ___________________________________________________________________________________________________________ > > Please do not print this e-mail until urgent requirement. Go Green!! > Save Papers <=> Save Trees > > -- > 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. > -- 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.
