The largest number can be formed from the given number

Given a number write an algorithm to construct the largest number possible by using the digits of given number. Given number could be a negative number as well. 

Example:

Given Input: 34277765
Output: 77765432

Given Input: -342765
Output: -234567

Given Input: 0
Output: 0

Given Input: 2034
Output: 4320

Approach: Sorting

Check if the given number is negative and mark isNegative = true or false accordingly.

Get all the digits of the given number and sort these numbers in ascending order if isNegative = true or sort in descending order if isNegative = false. Now construct the number from the sort order. Multiply the final result with -1 if isNegative = true.

Time Complexity: O(nlogn)

Complete Code:

Output:

Given Input: 34277765
Largest Integer can be formed: 77765432
-------------------------------------
Given Input: -342765
Largest Integer can be formed: -234567
-------------------------------------
Given Input: 0
Largest Integer can be formed: 0
-------------------------------------
Given Input: 2034
Largest Integer can be formed: 4320


Counting Approach:

  • Check if the given number is negative and mark isNegative = true or false accordingly. 
  • Initialize a count [] array of size 10. (for digits 0 to 9). 
  • Get all the digits of the given number and store these in count[] with their counts in the given array.
  • Initialize int result = 0.
  • Now Iterate the array from 0 to 9 (if isNegative=true) or 9 to 0(if isNegative = false) and for each index do the below
    •  while count[index]>0
      • result = result * 10;
      • result +=index;
      • count[index]–;
  • Multiply the final result with -1 if isNegative = true 

Time Complexity: O(n)

Complete Code:

Output:

Given Input: 34277765
Largest Integer can be formed: 77765432
-------------------------------------
Given Input: -342765
Largest Integer can be formed: -234567
-------------------------------------
Given Input: 0
Largest Integer can be formed: 0
-------------------------------------
Given Input: 2034
Largest Integer can be formed: 4320

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.