|
This post is completed by 1 user
|
Add to List |
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]--;
- while count[index]>0
- 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