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.
