Last updated on January 14th, 2025 at 06:28 am
Here, we see an Integer to English Words LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Math, String
Companies
Facebook, Microsoft
Level of Question
Hard
Integer to English Words LeetCode Solution
Table of Contents
1. Problem Statement
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”
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Divide and Conquer”. The problem of converting a number to words is broken down into smaller subproblems (e.g., handling billions, millions, thousands, hundreds, tens, and units) and solved recursively.
3. Code Implementation in Different Languages
3.1 Integer to English Words C++
class Solution {
public:
string numberToWords(int num) {
if(num == 0) return "Zero";
else return int_string(num).substr(1);
}
private:
static const char * const below_20[];
static const char * const below_100[];
static string int_string(int num) {
if(num >= 1000000000) return int_string(num / 1000000000) + " Billion" + int_string(num - 1000000000 * (num / 1000000000));
else if(num >= 1000000) return int_string(num / 1000000) + " Million" + int_string(num - 1000000 * (num / 1000000));
else if(num >= 1000) return int_string(num / 1000) + " Thousand" + int_string(num - 1000 * (num / 1000));
else if(num >= 100) return int_string(num / 100) + " Hundred" + int_string(num - 100 * (num / 100));
else if(num >= 20) return string(" ") + below_100[num / 10 - 2] + int_string(num - 10 * (num / 10));
else if(num >= 1) return string(" ") + below_20[num - 1];
else return "";
}
};
const char * const Solution::below_20[] = {"One", "Two", "Three", "Four","Five","Six","Seven","Eight","Nine","Ten", "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
const char * const Solution::below_100[] = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
3.2 Integer to English Words Java
class Solution {
private final String[] belowTwenty = {"", "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"};
public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
return helper(num);
}
private String helper(int num) {
StringBuilder result = new StringBuilder();
if (num < 20) {
result.append(belowTwenty[num]);
} else if (num < 100) {
result.append(tens[num / 10]).append(" ").append(belowTwenty[num % 10]);
} else if (num < 1000) {
result.append(helper(num / 100)).append(" Hundred ").append(helper(num % 100));
} else if (num < 1000000) {
result.append(helper(num / 1000)).append(" Thousand ").append(helper(num % 1000));
} else if (num < 1000000000) {
result.append(helper(num / 1000000)).append(" Million ").append(helper(num % 1000000));
} else {
result.append(helper(num / 1000000000)).append(" Billion ").append(helper(num % 1000000000));
}
return result.toString().trim();
}
}
3.3 Integer to English Words JavaScript
var numberToWords = function(num) {
if (num === 0) {
return 'Zero';
}
if (num <= 20) {
return translations.get(num);
}
let result = [];
for (let [value, translation] of translations) {
const times = Math.floor(num / value);
if (times === 0) {
continue;
}
num -= times * value;
if (times === 1 && value >= 100) {
result.push('One', translation);
continue;
}
if (times === 1) {
result.push(translation);
continue;
}
result.push(numberToWords(times), translation);
}
return result.join(' ');
};
const translations = new Map([
[1000000000, 'Billion'],
[1000000, 'Million'],
[1000, 'Thousand'],
[100, 'Hundred'],
[90, 'Ninety'],
[80, 'Eighty'],
[70, 'Seventy'],
[60, 'Sixty'],
[50, 'Fifty'],
[40, 'Forty'],
[30, 'Thirty'],
[20, 'Twenty'],
[19, 'Nineteen'],
[18, 'Eighteen'],
[17, 'Seventeen'],
[16, 'Sixteen'],
[15, 'Fifteen'],
[14, 'Fourteen'],
[13, 'Thirteen'],
[12, 'Twelve'],
[11, 'Eleven'],
[10, 'Ten'],
[9, 'Nine'],
[8, 'Eight'],
[7, 'Seven'],
[6, 'Six'],
[5, 'Five'],
[4, 'Four'],
[3, 'Three'],
[2, 'Two'],
[1, 'One'],
]);
3.4 Integer to English Words Python
class Solution(object):
def numberToWords(self, num):
to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
def words(n):
if n < 20:
return to19[n-1:n]
if n < 100:
return [tens[n/10-2]] + words(n%10)
if n < 1000:
return [to19[n/100-1]] + ['Hundred'] + words(n%100)
for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
if n < 1000**(p+1):
return words(n/1000**p) + [w] + words(n%1000**p)
return ' '.join(words(num)) or 'Zero'
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(d) | O(d) |
| Java | O(d) | O(d) |
| JavaScript | O(d) | O(d) |
| Python | O(d) | O(d) |
where d is the number of digits in the input number.
- Constant Magnitude Levels: The recursion depth is limited to the number of magnitude levels (billions, millions, thousands, etc.), which is constant (4 levels).
- String Concatenation: The space complexity includes the space required for the result string, which grows linearly with the number of digits in the input number.
- Efficiency: The algorithm is efficient for typical integer inputs, as the recursion depth is bounded and the processing of each digit is straightforward.