Largest number by rearranging digits of a given positive or negative number

0 0 5 minutes read

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 number
long 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 code
int main()
{
    int N = -38290367;
 
    // Function call
    cout << printMaxNum(N);
    return 0;
}

Java

// Java program to implement the approach
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[(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 number
def 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 code
N = -38290367
 
# Function call
print(printMaxNum(N))
 
# This code is contributed by Taranpreet

C#

// C# program to implement the approach
using 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 code
var N = -38290367;
 
// Function call
document.write(printMaxNum(N));
 
// This code is contributed by shikhasingrajput 
</script>

Output

-20336789

Time Complexity: O( length(N) )
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!