Given an array of integers arr[] representing digits of a number. The task is to write a program to generate the largest number possible using these digits.
Note : The digits in the array are in between 0 and 9. That is, 0<arr[i]<9.
Examples :
Input : arr[] = {4, 7, 9, 2, 3} Output : Largest number: 97432 Input : arr[] = {8, 6, 0, 4, 6, 4, 2, 7} Output : Largest number: 87664420
Naive Approach : The naive approach is to sort the given array of digits in descending order and then form the number using the digits in array keeping the order of digits in the number same as that of the sorted array.
Time Complexity: O(N logN), where N is the number of digits.
Below is the implementation of above idea:
// C++ program to generate largest possible
// number with given digits
#include <bits/stdc++.h>
using
namespace
std;
// Function to generate largest possible
// number with given digits
int
findMaxNum(
int
arr[],
int
n)
{
`` // sort the given array in
`` // descending order
`` sort(arr, arr+n, greater<
int
>());
``
`` int
num = arr[0];
``
`` // generate the number
`` for
(
int
i=1; i<n; i++)
`` {
`` num = num*10 + arr[i];
`` }
``
`` return
num;
}
// Driver code
int
main()
{
`` int
arr[] = {1, 2, 3, 4, 5, 0};
``
`` int
n =
sizeof
(arr)/
sizeof
(arr[0]);
``
`` cout<<findMaxNum(arr,n);
``
`` return
0;
}
Output:
543210
Efficient Approach : An efficient approach is to observe that we have to form the number using only digits from 0-9. Hence we can create a hash of size 10 to store the number of occurrences of the digits in the given array into the hash table. Where the key in the hash table will be digits from 0 to 9 and their values will be the count of their occurrences in the array.
Finally, print the digits the number of times they occur in descending order starting from the digit 9.
Below is the implementation of above approach:
// C++ program to generate largest possible
// number with given digits
#include <bits/stdc++.h>
using
namespace
std;
// Function to generate largest possible
// number with given digits
void
findMaxNum(
int
arr[],
int
n)
{
`` // Declare a hash array of size 10
`` // and initialize all the elements to zero
`` int
hash[10] = {0};
``
`` // store the number of occurrences of the digits
`` // in the given array into the hash table
`` for
(
int
i=0; i<n; i++)
`` {
`` hash[arr[i]]++;
`` }
``
`` // Traverse the hash in descending order
`` // to print the required number
`` for
(
int
i=9; i>=0; i--)
`` {
`` // Print the number of times a digits occurs
`` for
(
int
j=0; j<hash[i]; j++)
`` cout<<i;
`` }
}
// Driver code
int
main()
{
`` int
arr[] = {1, 2, 3, 4, 5, 0};
``
`` int
n =
sizeof
(arr)/
sizeof
(arr[0]);
``
`` findMaxNum(arr,n);
``
`` return
0;
}
Output:
543210
Time Complexity : O(N), where N is the number of digits.
Auxiliary Space : O(1), size of hash is only 10 which is a constant.