Dada una array arr[] que contiene N enteros no negativos, la tarea es ordenar estos enteros según la suma del número de letras necesarias para representarlos.
Ejemplos:
Entrada: arr[] = {12, 10, 31, 18}
Salida: 12 31 10 18
Explicación:
12 -> uno + dos -> 3 + 3 = 6
31 -> tres + uno -> 4 + 3 = 7
10 -> uno + cero -> 3 + 4 = 7
18 -> uno + ocho -> 3 + 5 = 8Entrada: arr[] = {12, 10}
Salida: 12 10
Explicación:
12 -> uno + dos -> 3 + 3 = 6
10 -> uno + cero -> 3 + 4 = 7
Acercarse:
- Inicialmente, se define una array de tamaño diez que contiene el número de letras necesarias para representar cada dígito.
- Ahora, la array dada se itera y para cada número, se encuentra la cantidad de letras requeridas para representarlos.
- Ahora, este recuento total de caracteres y el número se suman a un par de vectores .
- Finalmente, este par de vectores se ordena en orden ascendente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to sort the strings
// based on the numbers of letters
// required to represent them
#include <bits/stdc++.h>
using namespace std;
// letters[i] stores the count of letters
// required to represent the digit i
const int letters[] = { 4, 3, 3, 3, 4,
4, 3, 5, 5, 4 };
// Function to return the sum of
// letters required to represent N
int sumOfLetters(int n)
{
int sum = 0;
while (n > 0) {
sum += letters[n % 10];
n = n / 10;
}
return sum;
}
// Function to sort the array according to
// the sum of letters to represent n
void sortArr(int arr[], int n)
{
// Vector to store the digit sum
// with respective elements
vector<pair<int, int> > vp;
// Inserting digit sum with elements
// in the vector pair
for (int i = 0; i < n; i++) {
// Making the vector pair
vp.push_back(
make_pair(
sumOfLetters(
arr[i]),
arr[i]));
}
// Sort the vector, this will sort the
// pair according to the sum of
// letters to represent n
sort(vp.begin(), vp.end());
// Print the sorted vector content
for (int i = 0; i < vp.size(); i++)
cout << vp[i].second << " ";
}
// Driver code
int main()
{
int arr[] = { 12, 10, 31, 18 };
int n = sizeof(arr) / sizeof(arr[0]);
sortArr(arr, n);
return 0;
}
Java
// Java program to sort the strings
// based on the numbers of letters
// required to represent them
import java.util.*;
import java.lang.*;
class GFG{
// letters[i] stores the count of letters
// required to represent the digit i
static int letters[] = { 4, 3, 3, 3, 4,
4, 3, 5, 5, 4 };
// Function to return the sum of
// letters required to represent N
static int sumOfLetters(int n)
{
int sum = 0;
while (n > 0)
{
sum += letters[n % 10];
n = n / 10;
}
return sum;
}
// Function to sort the array according to
// the sum of letters to represent n
static void sortArr(int arr[], int n)
{
// Vector to store the digit sum
// with respective elements
ArrayList<int[]> vp = new ArrayList<>();
// Inserting digit sum with elements
// in the vector pair
for(int i = 0; i < n; i++)
{
// Making the vector pair
vp.add(new int[]{sumOfLetters(arr[i]),
arr[i]});
}
// Sort the vector, this will sort the
// pair according to the sum of
// letters to represent n
Collections.sort(vp, (a, b) -> a[0] - b[0]);
// Print the sorted vector content
for(int i = 0; i < vp.size(); i++)
System.out.print(vp.get(i)[1] + " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12, 10, 31, 18 };
int n = arr.length;
sortArr(arr, n);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to sort the strings # based on the numbers of letters # required to represent them # letters[i] stores the count of letters # required to represent the digit i letters = [4, 3, 3, 3, 4, 4, 3, 5, 5, 4] # Function to return the sum of # letters required to represent N def sumOfLetters(n): sum = 0 while (n > 0): sum += letters[n % 10] n = n // 10 return sum # Function to sort the array according to # the sum of letters to represent n def sortArr(arr, n): # List to store the digit sum # with respective elements vp = [] # Inserting digit sum with elements # in the list pair for i in range(n): vp.append([sumOfLetters(arr[i]), arr[i]]) # Sort the list, this will sort the # pair according to the sum of # letters to represent n vp.sort(key = lambda x : x[0]) # Print the sorted list content for i in vp: print(i[1], end = " ") # Driver code if __name__ == '__main__': arr = [ 12, 10, 31, 18 ] n = len(arr) sortArr(arr, n) # This code is contributed by Shivam Singh
Javascript
<script>
// Javascript program to sort the strings
// based on the numbers of letters
// required to represent them
// letters[i] stores the count of letters
// required to represent the digit i
let letters = [ 4, 3, 3, 3, 4,
4, 3, 5, 5, 4 ];
// Function to return the sum of
// letters required to represent N
function sumOfLetters( n)
{
let sum = 0;
while (n > 0)
{
sum += letters[n % 10];
n = Math.floor(n / 10);
}
return sum;
}
// Function to sort the array according to
// the sum of letters to represent n
function sortArr(arr, n)
{
// Vector to store the digit sum
// with respective elements
let vp = [];
// Inserting digit sum with elements
// in the vector pair
for(let i = 0; i < n; i++)
{
// Making the vector pair
vp.push([sumOfLetters(arr[i]),
arr[i]]);
}
// Sort the vector, this will sort the
// pair according to the sum of
// letters to represent n
vp.sort((a, b) => a[0] - b[0]);
// Print the sorted vector content
for(let i = 0; i < vp.length; i++)
document.write(vp[i][1] + " ");
}
// Driver Code
let arr = [ 12, 10, 31, 18 ];
let n = arr.length;
sortArr(arr, n);
</script>
Producción:
12 31 10 18
Complejidad de tiempo: O(N * log(N)) , donde N es el tamaño de la array.