Given a number, write a program to find a maximum number that can be formed using all of the digits of this number.
Examples:
Input : 38293367 Output : 98763332 Input : 1203465 Output: 6543210
Simple Approach: The simple method to solve this problem is to extract and store the digits of the given number in an integer array and sort this array in descending order. After sorting the array, print the elements of the array.
Time Complexity: O( N log N ), where N is the number of digits in the given number.
Efficient approach : We know that the digits in a number will range from 0-9, so the idea is to create a hashed array of size 10 and store the count of every digit in the hashed array that occurs in the number. Then traverse the hashed array from index 9 to 0 and calculate the number accordingly.
Below is the implementation of above efficient approach:
C++
// CPP program to print the maximum number// from the set of digits of a given number#include <bits/stdc++.h>using namespace std;// Function to print the maximum numberint printMaxNum(int num){ // hashed array to store count of digits int count[10] = {0}; // Converting given number to string string str = to_string(num); // Updating the count array for (int i=0; i<str.length(); i++) count[str[i]-'0']++; // result is to store the final number int result = 0, multiplier = 1; // Traversing the count array // to calculate the maximum number for (int i = 0; i <= 9; i++) { while (count[i] > 0) { result = result + (i * multiplier); count[i]--; multiplier = multiplier * 10; } } // return the result return result;}// Driver program to test above functionint main(){ int num = 38293367; cout << printMaxNum(num); return 0;} |
Java
// Java program to print the maximum number// from the set of digits of a given numberpublic class GFG{ // Function to print the maximum number static int printMaxNum(int num) { // hashed array to store count of digits int count[] = new int[10]; // Converting given number to string String str = Integer.toString(num); // Updating the count array for(int i=0; i < str.length(); i++) count[str.charAt(i)-'0']++; // result is to store the final number int result = 0, multiplier = 1; // Traversing the count array // to calculate the maximum number for (int i = 0; i <= 9; i++) { while (count[i] > 0) { result = result + (i * multiplier); count[i]--; multiplier = multiplier * 10; } } // return the result return result; } // Driver program to test above function public static void main(String[] args) { int num = 38293367; System.out.println(printMaxNum(num)); }}// This code is contributed by Sumit Ghosh |
Python3
# Python program to print the maximum number# from the set of digits of a given number# Function to print maximum numberdef printMaximum(inum): # Hashed array to store count of digits count = [0 for x in range(10)] # Converting given number to string string = str(num) # Updating the count array for i in range(len(string)): count[int(string[i])] = count[int(string[i])] + 1 # Result stores final number result = 0 multiplier = 1 # traversing the count array # to calculate the maximum number for i in range(10): while count[i] > 0: result = result + ( i * multiplier ) count[i] = count[i] - 1 multiplier = multiplier * 10 # return the result return result# Driver codenum = 38293367print(printMaximum(num))# This code is contributed by Harshit Agrawal |
C#
// C# program to print the maximum number// from the set of digits of a given numberusing System;class GFG { // Function to print the maximum numberstatic int printMaxNum(int num){ // hashed array to store // count of digits int []count = new int[10]; // Converting given number // to string String str = num.ToString(); // Updating the count array for(int i = 0; i < str.Length; i++) count[str[i] - '0']++; // result is to store the // final number int result = 0, multiplier = 1; // Traversing the count array // to calculate the maximum number for (int i = 0; i <= 9; i++) { while (count[i] > 0) { result = result + (i * multiplier); count[i]--; multiplier = multiplier * 10; } } // return the result return result;}// Driver Codepublic static void Main() { int num = 38293367; Console.Write(printMaxNum(num));}}// This code is contributed // by PrinciRaj1992 |
PHP
<?php// Php program to print the maximum number// from the set of digits of a given number// Function to print the maximum numberfunction printMaxNum($num){ // hashed array to store count of digits $count = array_fill(0,10, NULL); // Converting given number to string $str = (string)$num; // Updating the count array for ($i=0; $i<strlen($str); $i++) $count[ord($str[$i])-ord('0')]++; // result is to store the final number $result = 0; $multiplier = 1; // Traversing the count array // to calculate the maximum number for ($i = 0; $i <= 9; $i++) { while ($count[$i] > 0) { $result = $result + ($i * $multiplier); $count[$i]--; $multiplier = $multiplier * 10; } } // return the result return $result;} // Driver program to test above function $num = 38293367; echo printMaxNum($num);?> |
Javascript
<script>// Javascript program to print the maximum number// from the set of digits of a given number // Function to print the maximum number function printMaxNum(num) { // hashed array to store count of digits let count = new Array(10); for(let i=0;i<count.length;i++) { count[i]=0; } // Converting given number to string let str = num.toString(); // Updating the count array for(let i=0; i < str.length; i++) count[str[i]-'0']++; // result is to store the final number let result = 0, multiplier = 1; // Traversing the count array // to calculate the maximum number for (let i = 0; i <= 9; i++) { while (count[i] > 0) { result = result + (i * multiplier); count[i]--; multiplier = multiplier * 10; } } // return the result return result; } // Driver program to test above function let num = 38293367; document.write(printMaxNum(num)); //This code is contributed by avanitrachhadiya2155 </script> |
Output:
98763332
Time Complexity: O( N ), where N is the number of digits in the given number.
Auxiliary Space: O(1)
Note: For very large numbers we can use strings to take input instead of storing input in integer data type.
This article is contributed by Rohit Thapliyal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
