This post is completed by 1 user

  • 1
 Add to List
Beginner

485. Construct the Largest number from the given digits

Given a set of digits, write an algorithm to construct the largest number possible by appending the given digits.

Example:

Given Digits: [9, 1, 9, 2, 8, 4, 2]
largest number: 9984221

Given Digits: [1, 2, 5, 6, 7]
largest number: 76521

Approach: Sorting

  • Sort the given array in descending order.
  • Initialize result = 0.
  • Iterate the digits from left to right and for each digit d-
    • result = result * 10 + d.
  • Return result.

Time Complexity: O(nlogn)

Output:

Given Digits: [9, 1, 9, 2, 8, 4, 2]
largest number: 9984221

Better Solution: Use a count array.

Create a count[] array of size 10. In this array, we will store the count for each digit. Count of digit 0 will be at index 0, count of digit 1 will be at index 1 and so on. Iterate the given array and fill the count[] array with each digits count. Initialize result = 0.

Then Iterate the count[] from index 9 to 0 and for count for each index, result = result * 10 + index.

Time Complexity: O(N)

Output:

Given Digits: [8, 1, 2, 5, 6, 7]
largest number: 876521

Related Problems: