Be the first user to complete this post

  • 0
Add to List
Medium

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