Print all numbers up to N in words in lexicographical order

0 0 6 minutes read

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 words
string 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 order
void 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 code
int 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 words
def 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 order
def 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 code
if __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 order
function 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 code
const 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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!