Beginner

# 498. 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)

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)

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

```