+ 1

Greedy algorithm (Find out maximum number)

Help me please problem :- I want to make max number out of digit Solution 1:- sort the list in descending order But the problem is if there are 2 digit 2 21 suppose So,ans is 212 But correct ans should be 221 Solution 2:- make permutations of given no and then find max but it is exceeding time limit of 5 sec Pls provide a approach . Example:- Input 9 4 6 1 9 Output:-99641 In this case normal sorting can be done and then reverse --------------------------------------------------- Example 2:- Input:-21 2 Output :- 221 If I used above algorithm ie sort >>2 21 Reverse>>212 The answer is wrong Output :- 221. ------------------------------------------------------------------------ Input:- 23 213 Output:-23213 https://code.sololearn.com/cOVy49jjv3rW/?ref=app https://code.sololearn.com/cYMyc7oxa12A/?ref=app

17th May 2020, 1:48 PM
Priyal Vyas
Priyal Vyas - avatar
57 Answers
+ 2
Guys: I coded my solution: have fun https://code.sololearn.com/cMfCYlv7SYzX/?ref=app
18th May 2020, 7:22 AM
Alexander Thiem
Alexander Thiem - avatar
+ 2
Seems to be correct👍👍
18th May 2020, 7:33 PM
Alexander Thiem
Alexander Thiem - avatar
25th May 2020, 3:32 PM
george
george - avatar
+ 1
You have to change the way it is sorted!! In the sort algorithm 2 has to be threaten as 22222222 and 21 as 2121212121.... Then 2 is bigger as 21..... Have fun
17th May 2020, 2:14 PM
Alexander Thiem
Alexander Thiem - avatar
+ 1
Priyal Look at my answer! It solves this
17th May 2020, 2:39 PM
Alexander Thiem
Alexander Thiem - avatar
+ 1
comment deleted....just realised what your actually trying to do.
17th May 2020, 4:18 PM
rodwynnejones
rodwynnejones - avatar
+ 1
You mean 100 Numbers??? Of course it is just O(n)+ sortalgorithm(with selfmace comparison function). So i Think it should work
17th May 2020, 6:22 PM
Alexander Thiem
Alexander Thiem - avatar
+ 1
Ok I will code it hopefully tomorrow....
17th May 2020, 6:25 PM
Alexander Thiem
Alexander Thiem - avatar
+ 1
𝐊𝐢𝐢𝐛𝐨 𝐆𝐡𝐚𝐲𝐚𝐥 I think this was the first approach only working for numbers<10
18th May 2020, 6:24 AM
Alexander Thiem
Alexander Thiem - avatar
+ 1
Priyal I think your new code would not work for 7 9 8 as input. Output 978 Suggested output 987
18th May 2020, 6:25 AM
Alexander Thiem
Alexander Thiem - avatar
+ 1
I tested both mine and the one you posted, mine took 10 time longer to run using 10 two digit numbers so need to think how else to do it.
18th May 2020, 6:25 AM
rodwynnejones
rodwynnejones - avatar
+ 1
That is what your code says, but it should be output : 232 You shpuöd not spöit the numbers
18th May 2020, 6:31 AM
Alexander Thiem
Alexander Thiem - avatar
+ 1
To be honest I dont knoe what happens with 098, but 5 67 98 26 1 will result in 98675261
18th May 2020, 6:35 AM
Alexander Thiem
Alexander Thiem - avatar
+ 1
You are not allowed to split the given numbers, so 7 is to the right of 6 every time... look at Priyal first posted code it gives the same result....
18th May 2020, 6:39 AM
Alexander Thiem
Alexander Thiem - avatar
+ 1
𝐊𝐢𝐢𝐛𝐨 𝐆𝐡𝐚𝐲𝐚𝐥 consider example 345 and 50 Now if sort it u will get is 34550 But the correct should one is 50345
18th May 2020, 7:22 AM
Priyal Vyas
Priyal Vyas - avatar
+ 1
Alexander Thiem yup correct solution .This is what you said yesterday thanks .Hats off!!
18th May 2020, 12:46 PM
Priyal Vyas
Priyal Vyas - avatar
18th May 2020, 12:46 PM
Priyal Vyas
Priyal Vyas - avatar
+ 1
you are welcome
18th May 2020, 1:01 PM
Alexander Thiem
Alexander Thiem - avatar
18th May 2020, 7:06 PM
ARUNACHALAM P V
ARUNACHALAM P V - avatar
+ 1
Is this correct
18th May 2020, 7:07 PM
ARUNACHALAM P V
ARUNACHALAM P V - avatar