Given an integer N(positive or negative), the task is to find the maximum number that can be formed using all of the digits of this number.
Examples:
Input: -38290367
Output: -20336789
Explanation: As there is need to use all the digits, 0 cannot be the first digit because it becomes redundant at first position.Input: 1203465
Output: 6543210
Â
Approach: The digits in a number will range from 0-9, so the idea is to create a hash array of size 10 and store the count of every digit in the hashed array that occurs in the number. Follow the steps mentioned below to solve the problem:Â
- Then first check if the number is positive or negative
- If the number is positive, then as explained in this article, traverse the hashed array from index 9 to 0 and calculate the number accordingly.
- But if the number is negative, traverse the array from 0-9, such that:
- There can be leading 0s. So, find the smallest non-zero digit present
- Insert the smallest non-zero digit in the start, and then add all other digits from 0 to 9 in that order to the final answer
- Then multiply the number by -1 to make it negative
- Return the resultant number
Below is the implementation of the above approach
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;Â
// Function to print the maximum numberlong long printMaxNum(long long num){    // Initialising hash array    int hash[10] = { 0 };    long long n = num < 0 ? num * -1 : num;    long long ans = 0;    while (n) {        hash[n % 10]++;        n = n / 10;    }Â
    // If positive number    if (num > 0) {        for (int i = 9; i >= 0; i--)            for (int j = 0; j < hash[i]; j++)                ans = ans * 10 + i;    }Â
    // If negative number    else {Â
        // If 0 is present in the number        if (hash[0] > 0) {            for (int i = 1; i < 10; i++)                if (hash[i] > 0) {                    ans = i;                    hash[i]--;                    break;                }        }        for (int i = 0; i < 10; i++)            for (int j = 0; j < hash[i]; j++)                ans = ans * 10 + i;        ans = ans * -1;    }    return ans;}Â
// Driver codeint main(){Â Â Â Â int N = -38290367;Â
    // Function call    cout << printMaxNum(N);    return 0;} |
Java
// Java program to implement the approachclass GFG {Â
  // Function to print the maximum number  static long printMaxNum(long num)  {Â
    // Initialising hash array    int[] hash = new int[10];    for (int i = 0; i < 10; i++) {      hash[i] = 0;    }    long n = num < 0 ? num * -1 : num;    long ans = 0;    while (n > 0) {      hash[(int)(n % 10)] += 1;      n = n / 10;    }Â
    // If positive number    if (num > 0) {      for (int i = 9; i >= 0; i--)        for (int j = 0; j < hash[i]; j++)          ans = ans * 10 + i;    }Â
    // If negative number    else {Â
      // If 0 is present in the number      if (hash[0] > 0) {        for (int i = 1; i < 10; i++)          if (hash[i] > 0) {            ans = i;            hash[i]--;            break;          }      }      for (int i = 0; i < 10; i++)        for (int j = 0; j < hash[i]; j++)          ans = ans * 10 + i;      ans = ans * -1;    }    return ans;  }Â
  // Driver code  public static void main(String args[])  {    int N = -38290367;Â
    // Function call    System.out.println(printMaxNum(N));  }}Â
// This code is contributed by gfgking |
Python3
# Python program to implement the approachÂ
# Function to print the maximum numberdef printMaxNum(num):Â
    # Initialising hash array    hash = []    for i in range(0, 10):        hash.append(0)Â
    if(num < 0):        n = num * -1    else:        n = numÂ
    ans = 0    while (n != 0):        hash[int(n % 10)] = hash[int(n % 10)] + 1        n = n // 10Â
    # If positive number    if (num > 0):        for i in range(9, -1, -1):            for j in range(0, hash[i]):                ans = ans * 10 + iÂ
    # If negative number    else:Â
        # If 0 is present in the number        if (hash[0] > 0):            for i in range(1, 10):                if (hash[i] > 0):                    ans = i                    hash[i] = hash[i]-1                    breakÂ
        for i in range(0, 10):            for j in range(0, hash[i]):                ans = ans * 10 + i        ans = ans * -1Â
    return ansÂ
# Driver codeN = -38290367Â
# Function callprint(printMaxNum(N))Â
# This code is contributed by Taranpreet |
C#
// C# program to implement the approachusing System;class GFG {    // Function to print the maximum number    static long printMaxNum(long num)    {        // Initialising hash array        int[] hash = new int[10];        for (int i = 0; i < 10; i++) {            hash[i] = 0;        }        long n = num < 0 ? num * -1 : num;        long ans = 0;        while (n > 0) {            hash[n % 10]++;            n = n / 10;        }Â
        // If positive number        if (num > 0) {            for (int i = 9; i >= 0; i--)                for (int j = 0; j < hash[i]; j++)                    ans = ans * 10 + i;        }Â
        // If negative number        else {Â
            // If 0 is present in the number            if (hash[0] > 0) {                for (int i = 1; i < 10; i++)                    if (hash[i] > 0) {                        ans = i;                        hash[i]--;                        break;                    }            }            for (int i = 0; i < 10; i++)                for (int j = 0; j < hash[i]; j++)                    ans = ans * 10 + i;            ans = ans * -1;        }        return ans;    }Â
    // Driver code    public static void Main()    {        int N = -38290367;Â
        // Function call        Console.Write(printMaxNum(N));    }}Â
// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// javascript program to implement the approachÂ
  // Function to print the maximum number  function printMaxNum(num)  {Â
    // Initialising hash array    var hash = Array.from({length: 10}, (_, i) => 0);    for (var i = 0; i < 10; i++) {      hash[i] = 0;    }    var n = num < 0 ? num * -1 : num;    var ans = 0;    while (n > 0) {      hash[parseInt(n % 10)] += 1;      n = parseInt(n / 10);    }Â
    // If positive number    if (num > 0) {      for (var i = 9; i >= 0; i--)        for (var j = 0; j < hash[i]; j++)          ans = ans * 10 + i;    }Â
    // If negative number    else {Â
      // If 0 is present in the number      if (hash[0] > 0) {        for (var i = 1; i < 10; i++)          if (hash[i] > 0) {            ans = i;            hash[i]--;            break;          }      }      for (var i = 0; i < 10; i++)        for (var j = 0; j < hash[i]; j++)          ans = ans * 10 + i;      ans = ans * -1;    }    return ans;  }Â
  // Driver codevar N = -38290367;Â
// Function calldocument.write(printMaxNum(N));Â
// This code is contributed by shikhasingrajput </script> |
Â
Â
Output
-20336789
Â
Time Complexity: O( length(N) )
Auxiliary Space: O(1)
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
