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
Recommended: Sort the numbers according to their sum of digits
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.