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
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
- Define arrays for ones (1-19), tens (20-90), and place values (thousand, million, billion)
- Handle special case when input is 0
- Process number in groups of three digits (1000s)
- For each group:
- Convert hundreds place
- Convert tens place
- Convert ones place
- Combine results with appropriate place value words
- 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
This approach uses StringBuilder for efficient string operations and implements a divide-and-conquer strategy to process the number in chunks.
Algorithm
- Define constant arrays for number words
- Handle zero case separately
- Divide number into billions, millions, thousands, and remainder
- Process each division using StringBuilder:
- Convert hundreds place
- Handle numbers less than 20 specially
- Process tens and ones separately for numbers >= 20
- Combine all parts with appropriate place values
- Return trimmed result
Walkthrough
We use StringBuilder to avoid inefficient string concatenations and divide the number into chunks of three digits for better organization:
class Solution { private final String[] LESS_THAN_20 = {"Zero", "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"; StringBuilder sb = new StringBuilder(); int billion = num / 1000000000; int million = (num % 1000000000) / 1000000; int thousand = (num % 1000000) / 1000; int rest = num % 1000; if (billion != 0) { sb.append(convertHundred(billion)).append(" Billion "); } if (million != 0) { sb.append(convertHundred(million)).append(" Million "); } if (thousand != 0) { sb.append(convertHundred(thousand)).append(" Thousand "); } if (rest != 0) { sb.append(convertHundred(rest)); } return sb.toString().trim(); } private String convertHundred(int num) { StringBuilder sb = new StringBuilder(); int hundred = num / 100; int rest = num % 100; if (hundred != 0) { sb.append(LESS_THAN_20[hundred]).append(" Hundred "); } if (rest < 20) { if (rest != 0) { sb.append(LESS_THAN_20[rest]).append(" "); } } else { int tensDigit = rest / 10; int onesDigit = rest % 10; sb.append(TENS[tensDigit]).append(" "); if (onesDigit != 0) { sb.append(LESS_THAN_20[onesDigit]).append(" "); } } return sb.toString(); }}This implementation divides the number into billions, millions, thousands, and hundreds places, processing each separately using StringBuilder for efficient string manipulation.
Complexity
Time
O(n), where n is the number of digits in the input number
Space
O(1) for fixed-size arrays and StringBuilder
Trade-offs
Pros
More efficient string manipulation using StringBuilder
Better organized code structure
Cleaner handling of different number ranges
Reduced memory allocation compared to string concatenation
Cons
Slightly more complex implementation
Still requires careful handling of edge cases
Need to manage StringBuilder operations carefully
Solutions
Solution
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 ); } } }class Solution {private static Map<Integer, String> map; static { map = new HashMap<>(); map.put(1, "One"); map.put(2, "Two"); map.put(3, "Three"); map.put(4, "Four"); map.put(5, "Five"); map.put(6, "Six"); map.put(7, "Seven"); map.put(8, "Eight"); map.put(9, "Nine"); map.put(10, "Ten"); map.put(11, "Eleven"); map.put(12, "Twelve"); map.put(13, "Thirteen"); map.put(14, "Fourteen"); map.put(15, "Fifteen"); map.put(16, "Sixteen"); map.put(17, "Seventeen"); map.put(18, "Eighteen"); map.put(19, "Nineteen"); map.put(20, "Twenty"); map.put(30, "Thirty"); map.put(40, "Forty"); map.put(50, "Fifty"); map.put(60, "Sixty"); map.put(70, "Seventy"); map.put(80, "Eighty"); map.put(90, "Ninety"); map.put(100, "Hundred"); map.put(1000, "Thousand"); map.put(1000000, "Million"); map.put(1000000000, "Billion"); }public String numberToWords(int num) { if (num == 0) { return "Zero"; } StringBuilder sb = new StringBuilder(); for (int i = 1000000000; i >= 1000; i /= 1000) { if (num >= i) { sb.append(get3Digits(num / i)).append(' ').append(map.get(i)); num %= i; } } if (num > 0) { sb.append(get3Digits(num)); } return sb.substring(1); }private String get3Digits(int num) { StringBuilder sb = new StringBuilder(); if (num >= 100) { sb.append(' ') .append(map.get(num / 100)) .append(' ') .append(map.get(100)); num %= 100; } if (num > 0) { if (num < 20 || num % 10 == 0) { sb.append(' ').append(map.get(num)); } else { sb.append(' ') .append(map.get(num / 10 * 10)) .append(' ') .append(map.get(num % 10)); } } return sb.toString(); }}function numberToWords ( num ) { if ( num === 0 ) return ' Zero ' ; // prettier-ignore const f = ( x ) => { const dict1 = [ '' , ' One ' , ' Two ' , ' Three ' , ' Four ' , ' Five ' , ' Six ' , ' Seven ' , ' Eight ' , ' Nine ' , ' Ten ' , ' Eleven ' , ' Twelve ' , ' Thirteen ' , ' Fourteen ' , ' Fifteen ' , ' Sixteen ' , ' Seventeen ' , ' Eighteen ' , ' Nineteen ' ,] const dict2 = [ '' , '' , ' Twenty ' , ' Thirty ' , ' Forty ' , ' Fifty ' , ' Sixty ' , ' Seventy ' , ' Eighty ' , ' Ninety ' ,] let ans = '' if ( x <= 19 ) ans = dict1 [ x ] ?? '' else if ( x < 100 ) ans = ` ${ dict2 [ Math . floor ( x / 10 )]} ${ f ( x % 10 )} ` else if ( x < 10 ** 3 ) ans = ` ${ dict1 [ Math . floor ( x / 100 )]} Hundred ${ f ( x % 100 )} ` else if ( x < 10 ** 6 ) ans = ` ${ f ( Math . floor ( x / 10 ** 3 ))} Thousand ${ f ( x % 10 ** 3 )} ` else if ( x < 10 ** 9 ) ans = ` ${ f ( Math . floor ( x / 10 ** 6 ))} Million ${ f ( x % 10 ** 6 )} ` else ans = ` ${ f ( Math . floor ( x / 10 ** 9 ))} Billion ${ f ( x % 10 ** 9 )} ` return ans . trim () } return f ( num ); }class Solution: def numberToWords(self, num: int) -> str: if num == 0: return 'Zero' lt20 = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen', ] tens = ['', 'Ten', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety', ] thousands = ['Billion', 'Million', 'Thousand', ''] def transfer(num): if num == 0: return '' if num < 20: return lt20[num] + ' ' if num < 100: return tens[num // 10] + ' ' + transfer(num % 10) return lt20[num // 100] + ' Hundred ' + transfer(num % 100) res = [] i, j = 1000000000, 0 while i > 0: if num // i != 0: res . append(transfer(num // i)) res . append(thousands[j]) res . append(' ') num %= i j += 1 i //= 1000 return '' . join(res). strip()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.