Sort Array of Non-Negative Integers by Sum of Letters

Given an array arr[] of N non-negative integers, the task is to sort these integers according to the sum of letters required to represent them.

Examples:

Input: arr[] = {12, 10, 31, 18} 
Output: 
12 31 10 18 12 -> one + two -> 3 + 3 = 6 31 -> three + one -> 4 + 3 = 7 10 -> one + zero -> 3 + 4 = 7 18 -> one + eight -> 3 + 5 = 8 

Input: arr[] = {12, 10} 
Output: 
12 10 12 -> one + two -> 3 + 3 = 6 10 -> one + zero -> 3 + 4 = 7

Approach:
The idea is to store each element with its sum of letters to represent n in a vector pair and then sort all the elements of the vector according to the sum of letters stored.
Finally, print the elements in order.

Below is the implementation of the above approach:

// C++ implementation of the approach
#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 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++) {
        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;
}

Output:

12 31 10 18

Time Complexity: O(nlogn)
Space Complexity: O(n)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.