Be the first user to complete this post
|
Add to List |
460. Construct the largest number from the given array
Objective: Given an array of integers, write an algorithm to construct the largest number possible by appending the array elements.
Example:
Given Input: [7, 78] Largest Number Possible: 787 Explanation: two possibilities are 778 and 787. 787 is larger than 778. Given Input: [25, 42, 39] Largest Number Possible: 423925
Approach:
- Normal sorting in descending order will not help here, let's take an example, [8, 71]. After sorting [71, 8] so number after appending would be 718 but the right answer is 871.
- We will sort according to the digits. Let's say two elements are [A, B], We will override the comparator and in comparison, compare AB and BA and if AB>BA then return -1 else return 1.
- Once the input array is sorted according to the above statement, iterate the input and append all the elements. This will be our largest number.
Output:
Given Input: [7, 78] Largest Number Possible: 787