Dada una array de enteros arr[] que representan los dígitos de un número. La tarea es escribir un programa para generar el mayor número posible utilizando estos dígitos.
Nota : Los dígitos de la array están entre 0 y 9. Es decir, 0<arr[i]<9.
Ejemplos :
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
Enfoque ingenuo : el enfoque ingenuo consiste en ordenar la array dada de dígitos en orden descendente y luego formar el número usando los dígitos en la array manteniendo el orden de los dígitos en el número igual al de la array ordenada.
Complejidad temporal: O(N logN), donde N es el número de dígitos.
A continuación se muestra la implementación de la idea anterior:
C++
// 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;
}
Java
// Java program to generate largest
// possible number with given digits
import java.*;
import java.util.Arrays;
class GFG
{
// Function to generate largest
// possible number with given digits
static int findMaxNum(int arr[], int n)
{
// sort the given array in
// ascending order and then
// traverse into descending
Arrays.sort(arr);
int num = arr[0];
// generate the number
for(int i = n - 1; i >= 0; i--)
{
num = num * 10 + arr[i];
}
return num;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 0};
int n = arr.length;
System.out.println(findMaxNum(arr, n));
}
}
// This code is contributed by mits
Python3
# Python3 program to generate largest possible # number with given digits # Function to generate largest possible # number with given digits def findMaxNum(arr,n) : # sort the given array in # descending order arr.sort(reverse = True) # initialize num with starting # element of an arr num = arr[0] # generate the number for i in range(1,n) : num = num * 10 + arr[i] return num # Driver code if __name__ == "__main__" : arr = [1,2,3,4,5,0] n = len(arr) print(findMaxNum(arr,n))
C#
// C# program to generate largest
// possible number with given digits
using System;
public class GFG{
// Function to generate largest
// possible number with given digits
static int findMaxNum(int []arr, int n)
{
// sort the given array in
// ascending order and then
// traverse into descending
Array.Sort(arr);
int num = arr[0];
// generate the number
for(int i = n - 1; i >= 0; i--)
{
num = num * 10 + arr[i];
}
return num;
}
// Driver code
static public void Main (){
int []arr = {1, 2, 3, 4, 5, 0};
int n = arr.Length;
Console.WriteLine(findMaxNum(arr, n));
}
}
// This code is contributed by Sachin..
PHP
<?php
// PHP program to generate
// largest possible number
// with given digits
// Function to generate
// largest possible number
// with given digits
function findMaxNum(&$arr, $n)
{
// sort the given array
// in descending order
rsort($arr);
$num = $arr[0];
// generate the number
for($i = 1; $i < $n; $i++)
{
$num = $num * 10 + $arr[$i];
}
return $num;
}
// Driver code
$arr = array(1, 2, 3, 4, 5, 0);
$n = sizeof($arr);
echo findMaxNum($arr,$n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to generate largest possible
// number with given digits
// Function to generate largest possible
// number with given digits
function findMaxNum(arr, n)
{
// sort the given array in
// descending order
arr.sort(function(a,b){return b-a;});
var num = arr[0];
// generate the number
for(var i=1; i<n; i++)
{
num = num*10 + arr[i];
}
return num;
}
// Driver code
var arr = [1, 2, 3, 4, 5, 0];
var n = arr.length;
document.write(findMaxNum(arr,n));
</script>
Producción:
543210
Enfoque eficiente : un enfoque eficiente es observar que tenemos que formar el número usando solo dígitos del 0 al 9. Por lo tanto, podemos crear un hash de tamaño 10 para almacenar el número de ocurrencias de los dígitos en la array dada en la tabla hash. Donde la clave en la tabla hash serán los dígitos del 0 al 9 y sus valores serán el conteo de sus ocurrencias en la array.
Finalmente, imprima los dígitos la cantidad de veces que ocurren en orden descendente a partir del dígito 9.
A continuación se muestra la implementación del enfoque anterior:
C++
// 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;
}
// This code is contributed by Sania Kumari Gupta
C
// C program to generate largest possible number with
// given digits
#include <stdio.h>
// 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++)
printf("%d", 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;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to generate largest possible number with
// given digits
class GFG {
// Function to generate largest possible number with
// given digits
static void findMaxNum(int arr[], int n)
{
// Declare a hash array of size 10 and initialize
// all the elements to zero
int[] hash = new int[10];
// 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++)
System.out.print(i);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 0 };
int n = arr.length;
findMaxNum(arr, n);
}
}
// This code is contributed by Sania Kumari Gupta
Python 3
# Python 3 program to generate # largest possible number # with given digits # Function to generate # largest possible number # with given digits def findMaxNum(arr, n): # Declare a hash array of # size 10 and initialize # all the elements to zero hash = [0] * 10 # store the number of occurrences # of the digits in the given array # into the hash table for i in range(n): hash[arr[i]] += 1 # Traverse the hash in # descending order to # print the required number for i in range(9, -1, -1): # Print the number of # times a digits occurs for j in range(hash[i]): print(i, end = "") # Driver code if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 0] n =len(arr) findMaxNum(arr,n) # This code is contributed # by ChitraNayal
C#
// C# program to generate
// largest possible number
// with given digits
using System;
class GFG
{
// Function to generate
// largest possible number
// with given digits
static void findMaxNum(int[] arr,
int n)
{
// Declare a hash array of
// size 10 and initialize
// all the elements to zero
int[] hash = new int[10];
// 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++)
Console.Write(i);
}
}
// Driver code
public static void Main()
{
int[] arr = {1, 2, 3, 4, 5, 0};
int n = arr.Length;
findMaxNum(arr,n);
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program to generate
// largest possible number
// with given digits
// Function to generate
// largest possible number
// with given digits
function findMaxNum($arr, $n)
{
// Declare a hash array of
// size 10 and initialize
// all the elements to zero
$hash = array_fill(0, 10, 0);
// store the number of occurrences
// of the digits in the given array
// into the hash table
for($i = 0; $i < $n; $i++)
$hash[$arr[$i]] += 1;
// Traverse the hash in
// descending order to
// print the required number
for($i = 9; $i >= 0; $i--)
// Print the number of
// times a digits occurs
for($j = 0; $j < $hash[$i]; $j++)
echo $i;
}
// Driver code
$arr = array(1, 2, 3, 4, 5, 0);
$n = sizeof($arr);
findMaxNum($arr,$n);
// This code is contributed
// by mits
?>
Javascript
<script>
// Javascript program to generate largest possible
// number with given digits
// Function to generate largest possible
// number with given digits
function findMaxNum( arr, n)
{
// Declare a hash array of size 10
// and initialize all the elements to zero
var hash = Array(10).fill(0);
// store the number of occurrences of the digits
// in the given array into the hash table
for(var i=0; i<n; i++)
{
hash[arr[i]]++;
}
// Traverse the hash in descending order
// to print the required number
for(var i=9; i>=0; i--)
{
// Print the number of times a digits occurs
for(var j=0; j<hash[i]; j++)
document.write(i);
}
}
// Driver code
var arr = [1, 2, 3, 4, 5, 0];
var n = arr.length;
findMaxNum(arr,n);
</script>
Producción:
543210
Complejidad temporal : O(N), donde N es el número de dígitos.
Espacio auxiliar : O (1), el tamaño del hash es solo 10, que es una constante.
Publicación traducida automáticamente
Artículo escrito por IshitaBhuiya1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA