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
Approach 01:
-
C++
-
Python
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
string numberToWords(int num) {
if (num == 0) {
return "Zero";
}
return convertToWords(num);
}
private:
vector<string> belowTwenty = {
"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine",
"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen",
"Seventeen", "Eighteen", "Nineteen"
};
vector<string> tens = {
"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"
};
string convertToWords(int num) {
if (num < 20) {
return belowTwenty[num];
} else if (num < 100) {
return tens[num / 10] + (num % 10 != 0 ? " " + belowTwenty[num % 10] : "");
} else if (num < 1000) {
return convertToWords(num / 100) + " Hundred" + (num % 100 != 0 ? " " + convertToWords(num % 100) : "");
} else if (num < 1000000) {
return convertToWords(num / 1000) + " Thousand" + (num % 1000 != 0 ? " " + convertToWords(num % 1000) : "");
} else if (num < 1000000000) {
return convertToWords(num / 1000000) + " Million" + (num % 1000000 != 0 ? " " + convertToWords(num % 1000000) : "");
} else {
return convertToWords(num / 1000000000) + " Billion" + (num % 1000000000 != 0 ? " " + convertToWords(num % 1000000000) : "");
}
}
};
class Solution:
def numberToWords(self, num: int) -> str:
if num == 0:
return "Zero"
belowTwenty = [
"",
"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",
]
def solve(num: int) -> str:
if num < 20:
s = belowTwenty[num]
elif num < 100:
s = tens[num // 10] + " " + belowTwenty[num % 10]
elif num < 1000:
s = solve(num // 100) + " Hundred " + solve(num % 100)
elif num < 1000000:
s = solve(num // 1000) + " Thousand " + solve(num % 1000)
elif num < 1000000000:
s = solve(num // 1000000) + " Million " + solve(num % 1000000)
else:
s = solve(num // 1000000000) + " Billion " + solve(num % 1000000000)
return s.strip()
return solve(num)
Time Complexity
- Recursive Calls:
The function
convertToWordsrecursively processes the number by dividing it into smaller parts (hundreds, thousands, millions, etc.). Each recursive call handles a part of the number, and the depth of recursion is proportional to the number of digits innum. Since each recursive call processes a portion of the number in constant time, the time complexity is \( O(\log_{10} \text{num}) \). - Overall Time Complexity:
The time complexity is \( O(\log_{10} \text{num}) \), where \text{num} is the input integer.
Space Complexity
- Recursive Call Stack:
The space complexity is influenced by the depth of the recursive call stack, which is \( O(\log_{10} \text{num}) \). This is due to the recursive function calls, each handling a part of the number.
- Overall Space Complexity:
The overall space complexity is \( O(\log_{10} \text{num}) \) due to the recursion stack space used.