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.
