Given an array arr[] containing N non-negative integers, the task is to sort these integers alphabetically when each number is converted into words.
Examples:
Input: arr[] = {12, 10, 102, 31, 15}
Output: 15 102 10 31 12
Explanation:
The above set of numbers are sorted alphabetically. That is:
15 -> Fifteen
102 -> One hundred and two
10 -> Ten
31 -> Thirty-one
12 -> TwelveInput: arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
Output: 8 5 4 9 1 7 6 10 3 2
Explanation:
The above set of numbers are sorted alphabetically. That is:
8 -> eight
5 -> five
4 -> four
9 -> nine
1 -> one
7 -> seven
6 -> six
10 -> ten
3 -> three
2 -> two
Approach: In order to sort the numbers alphabetically, we first need to convert the number to its word form. Therefore, the idea is to store each element along with its word form in a vector pair and then sort all the elements of the vector according to the corresponding words of the number. Therefore:
- Precompute and store the word forms of all the units digits in an array.
- Precompute and store the word forms of all the tens digits in another array.
- For all the remaining numbers greater than 2 digits, the number is divided and the word form is added.
- Iterate through every digit of the number in the array arr[] and store the corresponding word form of the numbers in a vector as a pair.
- Iterate through the vector and sort the vector according to the words.
- Finally, print the sorted order.
Below is the implementation of the above approach:
C++
// C++ program to sort an array of // integers alphabetically #include <bits/stdc++.h> using namespace std; // Variable to store the word form of // units digit and up to twenty string one[] = { "", "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine ", "ten ", "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " }; // Variable to store the word form of // tens digit string ten[] = { "", "", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " }; // Function to convert a two digit number // to the word by using the above defined arrays string numToWords(int n, string s) { string str = ""; // If n is more than 19, divide it if (n > 19) str += ten[n / 10] + one[n % 10]; else str += one[n]; // If n is non-zero if (n) str += s; return str; } // Function to print a given number in words string convertToWords(int n) { // Stores the word representation // of the given number n string out; // Handles digits at ten millions // and hundred millions places out += numToWords((n / 10000000), "crore "); // Handles digits at hundred thousands // and one millions places out += numToWords(((n / 100000) % 100), "lakh "); // Handles digits at thousands and // tens thousands places out += numToWords(((n / 1000) % 100), "thousand "); // Handles digit at hundreds places out += numToWords(((n / 100) % 10), "hundred "); if (n > 100 && n % 100) out += "and "; // Call the above function to convert // the number into words out += numToWords((n % 100), ""); return out; } // Function to sort the array according to // the albhabetical order void sortArr(int arr[], int n) { // Vector to store the number in words // with respective elements vector<pair<string, int> > vp; // Inserting number in words // with respective elements in vector pair for (int i = 0; i < n; i++) { vp.push_back(make_pair( convertToWords(arr[i]), arr[i])); } // Sort the vector, this will sort the pair // according to the alphabetical order. 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, 102, 31, 15 }; int n = sizeof(arr) / sizeof(arr[0]); sortArr(arr, n); return 0; } |
Java
// Java program to sort an array of // integers alphabetically import java.util.*; class GFG{ static class pair implements Comparable<pair> { String first; int second; public pair(String first, int second) { this.first = first; this.second = second; } @Override public int compareTo(pair o) { // TODO Auto-generated method stub return this.first.compareTo(o.first); } } // Variable to store the word form of // units digit and up to twenty static String one[] = { "", "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine ", "ten ", "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " }; // Variable to store the word form of // tens digit static String ten[] = { "", "", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " }; // Function to convert a two digit number // to the word by using the above defined arrays static String numToWords(int n, String s) { String str = ""; // If n is more than 19, divide it if (n > 19) str += ten[n / 10] + one[n % 10]; else str += one[n]; // If n is non-zero if (n>0) str += s; return str; } // Function to print a given number in words static String convertToWords(int n) { // Stores the word representation // of the given number n String out = ""; // Handles digits at ten millions // and hundred millions places out += numToWords((n / 10000000), "crore "); // Handles digits at hundred thousands // and one millions places out += numToWords(((n / 100000) % 100), "lakh "); // Handles digits at thousands and // tens thousands places out += numToWords(((n / 1000) % 100), "thousand "); // Handles digit at hundreds places out += numToWords(((n / 100) % 10), "hundred "); if (n > 100 && n % 100!=0) out += "and "; // Call the above function to convert // the number into words out += numToWords((n % 100), ""); return out; } // Function to sort the array according to // the albhabetical order static void sortArr(int arr[], int n) { // Vector to store the number in words // with respective elements Vector<pair> vp = new Vector<pair>(); // Inserting number in words // with respective elements in vector pair for (int i = 0; i < n; i++) { vp.add(new pair( convertToWords(arr[i]), arr[i])); } // Sort the vector, this will sort the pair // according to the alphabetical order. Collections.sort(vp); // Print the sorted vector content for (int i = 0; i < vp.size(); i++) System.out.print(vp.get(i).second+ " "); } // Driver code public static void main(String[] args) { int arr[] = { 12, 10, 102, 31, 15 }; int n = arr.length; sortArr(arr, n); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to sort an array of # integers alphabetically # Variable to store the word form of # units digit and up to twenty one = [ "", "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine ", "ten ", "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " ] # Variable to store the word form of # tens digit ten = [ "", "", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " ] # Function to convert a two digit number # to the word by using the above defined arrays def numToWords(n, s): st = "" # If n is more than 19, divide it if (n > 19): st += ten[n // 10] + one[n % 10] else: st += one[n] # If n is non-zero if (n): st += s return st # Function to print a given number in words def convertToWords(n): # Stores the word representation # of the given number n out = "" # Handles digits at ten millions # and hundred millions places out += numToWords((n // 10000000), "crore ") # Handles digits at hundred thousands # and one millions places out += numToWords(((n // 100000) % 100), "lakh ") # Handles digits at thousands and # tens thousands places out += numToWords(((n // 1000) % 100), "thousand ") # Handles digit at hundreds places out += numToWords(((n // 100) % 10), "hundred ") if (n > 100 and n % 100): out += "and " # Call the above function to convert # the number into words out += numToWords((n % 100), "") return out # Function to sort the array according to # the albhabetical order def sortArr(arr, n): # Vector to store the number in words # with respective elements vp = [] # Inserting number in words # with respective elements in vector pair for i in range(n): vp.append((convertToWords(arr[i]), arr[i])); # Sort the vector, this will sort the pair # according to the alphabetical order. vp.sort() # Print the sorted vector content for i in range(len(vp)): print (vp[i][1], end = " ") # Driver code if __name__ == "__main__": arr = [ 12, 10, 102, 31, 15 ] n = len(arr) sortArr(arr, n) # This code is contributed by chitranayal |
C#
// C# program to sort an array of // integers alphabetically using System; using System.Collections.Generic; public class GFG{ class pair : IComparable<pair> { public String first; public int second; public pair(String first, int second) { this.first = first; this.second = second; } public int CompareTo(pair o) { return this.first.CompareTo(o.first); } } // Variable to store the word form of // units digit and up to twenty static String []one = { "", "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine ", "ten ", "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " }; // Variable to store the word form of // tens digit static String []ten = { "", "", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " }; // Function to convert a two digit number // to the word by using the above defined arrays static String numToWords(int n, String s) { String str = ""; // If n is more than 19, divide it if (n > 19) str += ten[n / 10] + one[n % 10]; else str += one[n]; // If n is non-zero if (n>0) str += s; return str; } // Function to print a given number in words static String convertToWords(int n) { // Stores the word representation // of the given number n String Out = ""; // Handles digits at ten millions // and hundred millions places Out += numToWords((n / 10000000), "crore "); // Handles digits at hundred thousands // and one millions places Out += numToWords(((n / 100000) % 100), "lakh "); // Handles digits at thousands and // tens thousands places Out += numToWords(((n / 1000) % 100), "thousand "); // Handles digit at hundreds places Out += numToWords(((n / 100) % 10), "hundred "); if (n > 100 && n % 100!=0) Out += "and "; // Call the above function to convert // the number into words Out += numToWords((n % 100), ""); return Out; } // Function to sort the array according to // the albhabetical order static void sortArr(int []arr, int n) { // List to store the number in words // with respective elements List<pair> vp = new List<pair>(); // Inserting number in words // with respective elements in vector pair for (int i = 0; i < n; i++) { vp.Add(new pair( convertToWords(arr[i]), arr[i])); } // Sort the vector, this will sort the pair // according to the alphabetical order. vp.Sort(); // Print the sorted vector content for (int i = 0; i < vp.Count; i++) Console.Write(vp[i].second+ " "); } // Driver code public static void Main(String[] args) { int []arr = { 12, 10, 102, 31, 15 }; int n = arr.Length; sortArr(arr, n); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript implementation of the above approach // Variable to store the word form of // units digit and up to twenty var one = [ "", "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine ", "ten ", "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " ]; // Variable to store the word form of // tens digit var ten = ["", "", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " ]; // Function to convert a two digit number // to the word by using the above defined arrays function numToWords(n, s) { var str = ""; // If n is more than 19, divide it if (n > 19) str += ten[(Math.floor(n / 10))] + one[n % 10]; else str += one[n]; // If n is non-zero if (n) str += s; return str; } // Function to print a given number in words function convertToWords(n) { // Stores the word representation // of the given number n var out; // Handles digits at ten millions // and hundred millions places out += numToWords(Math.floor(n / 10000000), "crore "); // Handles digits at hundred thousands // and one millions places out += numToWords((Math.floor(n / 100000) % 100), "lakh "); // Handles digits at thousands and // tens thousands places out += numToWords((Math.floor(n / 1000) % 100), "thousand "); // Handles digit at hundreds places out += numToWords((Math.floor(n / 100) % 10), "hundred "); if (n > 100 && n % 100) out += "and "; // Call the above function to convert // the number into words out += numToWords((n % 100), ""); return out; } // Function to sort the array according to // the albhabetical order function sortArr(arr, n) { // Vector to store the number in words // with respective elements var vp = new Array(n); // Inserting number in words // with respective elements in vector pair for (var i = 0; i < n; i++) { vp[i] = [convertToWords(arr[i]), arr[i]]; } // Sort the vector, this will sort the pair // according to the alphabetical order. vp.sort(); // Print the sorted vector content for (var i = 0; i < n; i++) document.write(vp[i][1]+" "); } // Driver Code var arr = [ 12, 10, 102, 31, 15 ]; var n = arr.length; sortArr(arr, n); </script> |
Output:
15 102 10 31 12
Time Complexity: O(N * log(N)), where N is the size of the array
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
