Make Maximum Number

Moderate

0/80

Average time to solve is 18m

Contributed by

19 upvotes

Asked in companies

Problem statement

Given a linked list such that each node represents a digit. Construct the maximum number possible from the given digits.

You just need to print the maximum Integer that can be formed

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first and only line of each test case consists of Linked list elements of length n (separated by space and terminated by -1)

Output format :

The maximum Number that is formed using the digits present in the linked list.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= N  <= 10^6
0 <= data <= 9

Time Limit: 1sec

Sample Input 1 :

 1 2 2 0 9 -1

Sample Output 1 :

Explanation For Sample Input1:

The digits that are present in the linked list are : (1, 2, 2, 0, 9 )

So the answer is the maximum of all the numbers that are formed using these digits is 92210.

Sample Input 2 :

1 0 0 0 3 -1

Sample Output 2 :

Hint 1

Hint 2

Try to sort the numbers in the linked list in reverse order.

Approaches (2)

Approach 1

Approach 2

Sorting

Traverse in the linked list and store the elements in the vector or array, then sort the array or vector and then reverse the array or vector, return the number as string formed using the digits formed in the same order as in array or vector.

Time Complexity

O(N log(N)), where N is the length of Linked List

Since sorting is used to form the largest number from digits.

Space Complexity

O(N), where N is the length of Linked List

The extra space is used to create a vector of the same size as the length of the linked list.

(100% EXP penalty)

Make Maximum Number

Console