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