Scale Engineer

Integer to English Words

Hard
#0260Time: O(n), where n is the number of digits in the input numberSpace: O(1) as we use fixed-size arrays for word mappings13 companies
Patterns
MathRecursion
Data structures
String
Companies
RobloxSnowflakeZohoeBay

Prompt

Convert a non-negative integer num to its English words representation.

 

Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"

Example 2:

Input: num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: num = 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

 

Constraints:

  • 0 <= num <= 231 - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iteratively building the English words representation by processing each digit and concatenating strings.

Algorithm

  1. Define arrays for ones (1-19), tens (20-90), and place values (thousand, million, billion)
  2. Handle special case when input is 0
  3. Process number in groups of three digits (1000s)
  4. For each group:
    • Convert hundreds place
    • Convert tens place
    • Convert ones place
  5. Combine results with appropriate place value words
  6. Trim extra spaces and return result

Walkthrough

In this approach, we'll first define arrays for different number words (ones, tens, and special cases). Then we'll process the number digit by digit, building the result string:

class Solution {    private final String[] ONES = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",            "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};    private final String[] TENS = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};    private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};        public String numberToWords(int num) {        if (num == 0) return "Zero";                String words = "";        int i = 0;                while (num > 0) {            if (num % 1000 != 0) {                words = helper(num % 1000) + THOUSANDS[i] + " " + words;            }            num /= 1000;            i++;        }                return words.trim();    }        private String helper(int num) {        if (num == 0) return "";                if (num < 20) {            return ONES[num] + " ";        }                if (num < 100) {            return TENS[num/10] + " " + helper(num % 10);        }                return ONES[num/100] + " Hundred " + helper(num % 100);    }}

The solution breaks down the number into groups of three digits and processes each group separately. For each group, it handles hundreds, tens, and ones places using predefined arrays of word representations.

Complexity

Time

O(n), where n is the number of digits in the input number

Space

O(1) as we use fixed-size arrays for word mappings

Trade-offs

Pros

  • Simple and straightforward implementation

  • Easy to understand and maintain

  • Works well for small numbers

Cons

  • Uses string concatenation which can be inefficient for large numbers

  • Creates multiple intermediate string objects

  • Not very memory efficient due to string operations

Solutions

using System.Collections.Generic ; using System.Linq ; public class Solution { private string [] bases = { "Thousand" , "Million" , "Billion" }; public string NumberToWords ( int num ) { if ( num == 0 ) { return "Zero" ; } var baseIndex = - 1 ; var parts = new List < string >(); while ( num > 0 ) { var part = NumberToWordsInternal ( num % 1000 ); if ( part . Length > 0 && baseIndex >= 0 ) { part = JoinParts ( part , bases [ baseIndex ]); } parts . Add ( part ); baseIndex ++; num /= 1000 ; } parts . Reverse (); return JoinParts ( parts ); } private string JoinParts ( IEnumerable < string > parts ) { return string . Join ( " " , parts . Where ( p => p . Length > 0 )); } private string JoinParts ( params string [] parts ) { return JoinParts (( IEnumerable < string >) parts ); } private string NumberToWordsInternal ( int num ) { switch ( num ) { case 0 : return "" ; case 1 : return "One" ; case 2 : return "Two" ; case 3 : return "Three" ; case 4 : return "Four" ; case 5 : return "Five" ; case 6 : return "Six" ; case 7 : return "Seven" ; case 8 : return "Eight" ; case 9 : return "Nine" ; case 10 : return "Ten" ; case 11 : return "Eleven" ; case 12 : return "Twelve" ; case 13 : return "Thirteen" ; case 14 : return "Fourteen" ; case 15 : return "Fifteen" ; case 16 : return "Sixteen" ; case 17 : return "Seventeen" ; case 18 : return "Eighteen" ; case 19 : return "Nineteen" ; } if ( num < 100 ) { string part1 ; switch ( num / 10 ) { case 2 : part1 = "Twenty" ; break ; case 3 : part1 = "Thirty" ; break ; case 4 : part1 = "Forty" ; break ; case 5 : part1 = "Fifty" ; break ; case 6 : part1 = "Sixty" ; break ; case 7 : part1 = "Seventy" ; break ; case 8 : part1 = "Eighty" ; break ; case 9 : default : part1 = "Ninety" ; break ; } var part2 = NumberToWordsInternal ( num % 10 ); return JoinParts ( part1 , part2 ); } { var part1 = NumberToWordsInternal ( num / 100 ); var part2 = NumberToWordsInternal ( num % 100 ); return JoinParts ( part1 , "Hundred" , part2 ); } } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem