Sort strings according to numbers of matches required to represent them

Given an array arr[] of N strings, the task is to sort these strings according to the numbers of matches required to represent them.

Examples:

Input: 
arr[] = { "123", "46", "8", "88" } 
Output: 
8 46 123 88 
8 -> 7 sticks 46 -> 10 sticks 123 -> 12 sticks 88 -> 14 sticks 

Input: 
arr[] = { "65", "46", "800", "96" } 
Output: 
46 65 96 800

Approach:
The idea is to store each element with its number of matches required in a vector pair and then sort all the elements of the vector according to the number of matches required stored.
Finally, print the strings in order.

Below is the implementation of the above approach:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

// stick[i] stores the count of sticks 
// required to represent the digit i 
const int sticks[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; 

// Function to return the count of 
// matchsticks required to represent 
// the given number 
int countSticks(string str)
{ 
    int n = str.length();
    int cnt = 0; 
  
    // For every digit of the given number 
    for (int i = 0; i < n; i++) { 
  
        // Add the count of sticks required 
        // to represent the current digit 
        cnt += (sticks[str[i] - '0']); 
    } 
  
    return cnt; 
}

// Function to sort the array according to
// the number of matchsticks required to represent it.
void sortArr(string arr[], int n)
{
    // Vector to store the number of matchsticks 
    // required with respective elements
    vector<pair<int, string>> vp;

    // Inserting number of matchsticks with respective strings
    // in the vector pair
    for (int i = 0; i < n; i++) {
        vp.push_back(make_pair(countSticks(arr[i]), arr[i]));
    }

    // Sort the vector, this will sort the pair
    // according to the number of countSticks
    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()
{
    string arr[] = { "123", "46", "8", "88" };
    int n = sizeof(arr) / sizeof(arr[0]);

    sortArr(arr, n);

    return 0;
}

Output:

8 46 123 88

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

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.