as they havve different number of digits, we append 0 at the end after 1. so
the two numbers are 90,10 . after appending you get 901. Basically , i think
it is lexographic sorting ........
On Mon, Aug 15, 2011 at 12:05 AM, Kunal Patil <kp101...@gmail.com> wrote:
> 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 <dip10c...@gmail.com>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 <ankur.kkhur...@gmail.com> 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
>>> <puneet.nsi...@gmail.com>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 <ankur.kkhur...@gmail.com> 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 <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.
>>>> >
>>>> >
>>>>
>>>> --
>>>> 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.
>>>
>>
>>
>>
>> --
>>
>> ___________________________________________________________________________________________________________
>>
>> 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 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.
