Given an integer N, the task is to print all numbers from 1 to N (0 < N < 100000) in words in lexicographical order.
Examples :
Input: N = 11
Output: eight, eleven, five, four, nine, one, seven, six, three, two
Explanation:
The numbers from 1 to N is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.
Their respective representations in words are {one, two, three, four, five, six, seven, eight, nine, ten, eleven}.
Their correct lexicographical order is {eight, eleven, five, four, nine, one, seven, six, ten, three, two}.Input: N = 5
Output: five, four, one, three, two
Explanation:
The numbers from 1 to N is 1, 2, 3, 4, 5.
Their respective representations in words are {one, two, three, four, five}.
Their correct lexicographical order is {five, four, one, three, two}.
Approach: Follow the steps below to solve the problem:
- Initialize an array words[] of size N + 1 which stores the strings representations of each index from 1 to N at respective indices.
- Convert all numbers from 1 to N to words and store them at their corresponding indices.
- Sort the array words[] in ascending order.
- Print the elements present in the array words[].
Below is the implementation of the above approach:
C++
#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;// Function to convert a number to wordsstring number_to_words(int n) { // Stores the digits vector<string> ones {"","one","two","three","four","five","six","seven","eight","nine"}; vector<string> tens {"","","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"}; vector<string> teens {"ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"}; // Convert a two-digit number to words auto convert_two_digits = [&](int num) { if (num < 10) { return ones[num]; } else if (num < 20) { return teens[num-10]; } else { return tens[num/10] + (num%10==0 ? "" : " " + ones[num%10]); } }; // Convert a three-digit number to words auto convert_three_digits = [&](int num) { if (num < 100) { return convert_two_digits(num); } else { return ones[num/100] + " hundred" + (num%100==0 ? "" : " and " + convert_two_digits(num%100)); } }; // Convert a number to words if (n < 100) { return convert_two_digits(n); } else if (n < 1000) { return convert_three_digits(n); } else { return "number out of range"; }}// Function to print all the numbers up to n in lexicographical ordervoid print_numbers_in_words(int n) { // Convert all numbers to words vector<string> words; for (int i = 1; i <= n; i++) { words.push_back(number_to_words(i)); } // Sort all strings sort(words.begin(), words.end()); // Print the words in lexicographical order for (int i = 0; i < words.size(); i++) { cout << words[i] << ", "; }}// Driver codeint main() { int n = 15; print_numbers_in_words(n); return 0;} |
Java
import java.util.Arrays;public class NumberToWords { // Stores the digits private static final String[] ones = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; private static final String[] tens = {"", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"}; private static final String[] teens = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"}; // Convert a two-digit number to words private static String convertTwoDigits(int num) { if (num < 10) { return ones[num]; } else if (num < 20) { return teens[num - 10]; } else { return tens[num / 10] + (num % 10 == 0 ? "" : " " + ones[num % 10]); } } // Convert a three-digit number to words private static String convertThreeDigits(int num) { if (num < 100) { return convertTwoDigits(num); } else { return ones[num / 100] + " hundred" + (num % 100 == 0 ? "" : " and " + convertTwoDigits(num % 100)); } } // Convert a number to words public static String convertToWords(int num) { if (num < 100) { return convertTwoDigits(num); } else if (num < 1000) { return convertThreeDigits(num); } else { return "number out of range"; } } // Print all the numbers up to n in lexicographical order public static void printNumbersInWords(int n) { // Convert all numbers to words String[] words = new String[n]; for (int i = 1; i <= n; i++) { words[i - 1] = convertToWords(i); } // Sort all strings Arrays.sort(words); // Print the words in lexicographical order System.out.println(String.join(", ", words)); } // Driver code public static void main(String[] args) { int n = 15; printNumbersInWords(n); }} |
Python3
# Function to convert a number to wordsdef number_to_words(n): # Stores the digits ones = ['','one','two','three','four','five','six','seven','eight','nine'] tens = ['','','twenty','thirty','forty','fifty','sixty','seventy','eighty','ninety'] teens = ['ten','eleven','twelve','thirteen','fourteen','fifteen','sixteen','seventeen','eighteen','nineteen'] # Convert a two-digit number to words def convert_two_digits(num): if num < 10: return ones[num] elif num < 20: return teens[num-10] else: return tens[num//10] + ('' if num%10==0 else ' ' + ones[num%10]) # Convert a three-digit number to words def convert_three_digits(num): if num < 100: return convert_two_digits(num) else: return ones[num//100] + ' hundred' + ('' if num%100==0 else ' and ' + convert_two_digits(num%100)) # Convert a number to words if n < 100: return convert_two_digits(n) elif n < 1000: return convert_three_digits(n) else: return 'number out of range'# Function to print all the numbers up to n in lexicographical orderdef print_numbers_in_words(n): # Convert all numbers to words words=[] for i in range(1, n+1): words.append(number_to_words(i)) # Sort all strings words.sort() # Print the words in lexicographical order print(', '.join(words))# Driver codeif __name__ == "__main__": n = 15 print_numbers_in_words(n) |
C#
using System;using System.Collections.Generic;public class NumberToWords{ // Stores the digits private static readonly string[] Ones = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; private static readonly string[] Tens = {"", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"}; private static readonly string[] Teens = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"}; // Convert a two-digit number to words private static string ConvertTwoDigits(int num) { if (num < 10) { return Ones[num]; } else if (num < 20) { return Teens[num - 10]; } else { return Tens[num / 10] + (num % 10 == 0 ? "" : " " + Ones[num % 10]); } } // Convert a three-digit number to words private static string ConvertThreeDigits(int num) { if (num < 100) { return ConvertTwoDigits(num); } else { return Ones[num / 100] + " hundred" + (num % 100 == 0 ? "" : " and " + ConvertTwoDigits(num % 100)); } } // Convert a number to words public static string ConvertNumberToWords(int n) { if (n < 100) { return ConvertTwoDigits(n); } else if (n < 1000) { return ConvertThreeDigits(n); } else { return "number out of range"; } } // Print all the numbers up to n in lexicographical order public static void PrintNumbersInWords(int n) { // Convert all numbers to words List<string> words = new List<string>(); for (int i = 1; i <= n; i++) { words.Add(ConvertNumberToWords(i)); } // Sort all strings words.Sort(); // Print the words in lexicographical order Console.WriteLine(string.Join(", ", words)); } // Main method public static void Main(string[] args) { int n = 15; PrintNumbersInWords(n); }} |
Javascript
<script>function numberToWords(n) { // Stores the digits const ones = ['', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']; const tens = ['', '', 'twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety']; const teens = ['ten', 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen']; // Convert a two-digit number to words function convertTwoDigits(num) { if (num < 10) { return ones[num]; } else if (num < 20) { return teens[num - 10]; } else { return tens[Math.floor(num / 10)] + (num % 10 === 0 ? '' : ' ' + ones[num % 10]); } } // Convert a three-digit number to words function convertThreeDigits(num) { if (num < 100) { return convertTwoDigits(num); } else { return ones[Math.floor(num / 100)] + ' hundred' + (num % 100 === 0 ? '' : ' and ' + convertTwoDigits(num % 100)); } } // Convert a number to words if (n < 100) { return convertTwoDigits(n); } else if (n < 1000) { return convertThreeDigits(n); } else { return 'number out of range'; }}// Function to print all the numbers up to n in lexicographical orderfunction printNumbersInWords(n) { // Convert all numbers to words const words = []; for (let i = 1; i <= n; i++) { words.push(numberToWords(i)); } // Sort all strings words.sort(); // Print the words in lexicographical order console.log(words.join(', '));}// Driver codeconst n = 15;printNumbersInWords(n);</script> |
Output:
eight, eleven, fifteen, five, four, fourteen, nine, one, seven, six, ten, thirteen, three, twelve, two
Time Complexity: O(NlogN) where N is the given integer.
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!
