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!
