Encuentre el número más pequeño posible de un número grande dado con el mismo número de dígitos

Dado un número K de longitud N , la tarea es encontrar el número más pequeño posible que se pueda formar a partir de K de N dígitos intercambiando los dígitos cualquier número de veces. 

Ejemplos: 

Entrada: N = 15, K = 325343273113434 
Salida: 112233333344457 
Explicación: 
El número más pequeño posible después de intercambiar los dígitos del número dado es 112233333344457

Entrada: N = 7, K = 3416781 
Salida: 1134678 

Enfoque: La idea es utilizar Hashing . Para implementar el hash, se crea una array arr[] de tamaño 10. El número dado se itera y el recuento de ocurrencias de cada dígito se almacena en el hash en el índice correspondiente. Luego itere la array hash e imprima el i-ésimo dígito de acuerdo con su frecuencia. La salida será el menor número requerido de N dígitos.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the above approach
 
#include <iostream>
using namespace std;
 
// Function for finding the smallest
// possible number after swapping
// the digits any number of times
string smallestPoss(string s, int n)
{
    // Variable to store the final answer
    string ans = "";
 
    // Array to store the count of
    // occurrence of each digit
    int arr[10] = { 0 };
 
    // Loop to calculate the number
    // of occurrences of every digit
    for (int i = 0; i < n; i++) {
        arr[s[i] - 48]++;
    }
 
    // Loop to get smallest number
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < arr[i]; j++)
            ans = ans + to_string(i);
    }
 
    // Returning the answer
    return ans;
}
 
// Driver code
int main()
{
    int N = 15;
    string K = "325343273113434";
 
    cout << smallestPoss(K, N);
 
    return 0;
}

// Java implementation of the above approach
class GFG
{
 
// Function for finding the smallest
// possible number after swapping
// the digits any number of times
static String smallestPoss(String s, int n)
{
    // Variable to store the final answer
    String ans = "";
 
    // Array to store the count of
    // occurrence of each digit
    int arr[] = new int[10];
 
    // Loop to calculate the number
    // of occurrences of every digit
    for (int i = 0; i < n; i++)
    {
        arr[s.charAt(i) - 48]++;
    }
 
    // Loop to get smallest number
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < arr[i]; j++)
            ans = ans + String.valueOf(i);
    }
 
    // Returning the answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 15;
    String K = "325343273113434";
 
    System.out.print(smallestPoss(K, N));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the above approach
 
# Function for finding the smallest
# possible number after swapping
# the digits any number of times
def smallestPoss(s, n):
     
    # Variable to store the final answer
    ans = "";
 
    # Array to store the count of
    # occurrence of each digit
    arr = [0]*10;
 
    # Loop to calculate the number
    # of occurrences of every digit
    for i in range(n):
        arr[ord(s[i]) - 48] += 1;
     
    # Loop to get smallest number
    for i in range(10):
        for j in range(arr[i]):
            ans = ans + str(i);
     
    # Returning the answer
    return ans;
 
# Driver code
if __name__ == '__main__':
    N = 15;
    K = "325343273113434";
 
    print(smallestPoss(K, N));
 
# This code is contributed by 29AjayKumar

// C# implementation of the above approach
using System;
 
class GFG
{
 
// Function for finding the smallest
// possible number after swapping
// the digits any number of times
static String smallestPoss(String s, int n)
{
    // Variable to store the readonly answer
    String ans = "";
 
    // Array to store the count of
    // occurrence of each digit
    int []arr = new int[10];
 
    // Loop to calculate the number
    // of occurrences of every digit
    for (int i = 0; i < n; i++)
    {
        arr[s[i] - 48]++;
    }
 
    // Loop to get smallest number
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < arr[i]; j++)
            ans = ans + String.Join("",i);
    }
 
    // Returning the answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 15;
    String K = "325343273113434";
 
    Console.Write(smallestPoss(K, N));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation of the above approach
 
// Function for finding the smallest
// possible number after swapping
// the digits any number of times
function smallestPoss(s, n)
{
    // Variable to store the final answer
    var ans = "";
 
    // Array to store the count of
    // occurrence of each digit
    var arr = Array(10).fill(0);
 
    // Loop to calculate the number
    // of occurrences of every digit
    for (var i = 0; i < n; i++) {
        arr[s[i].charCodeAt(0) - 48]++;
    }
 
    // Loop to get smallest number
    for (var i = 0; i < 10; i++) {
        for (var j = 0; j < arr[i]; j++)
            ans = ans + i.toString();
    }
 
    // Returning the answer
    return ans;
}
 
// Driver code
var N = 15;
var K = "325343273113434";
document.write( smallestPoss(K, N));
 
</script>

112233333344457

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N + 10)