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