Given a non-negative integer num with at most four digits. Return its English words representation as a string.
Example 1
Input: num = 4027
Output: "four thousand twenty seven"
Explanation: 4027 contains four thousands, zero hundreds, two tens, and seven ones. The hundreds place contributes no words, and 27 contributes twenty seven.
Example 2
Input: num = 0
Output: "zero"
Explanation: Zero has its own word, so the result contains one word.
Approach
English number names follow place value from largest to smallest. A nonzero thousands or hundreds digit contributes its digit name followed by thousand or hundred. The last two digits form a smaller number with its own name.
That final number has two patterns. The numbers from one through nineteen have complete names, while larger two-digit numbers combine a tens name with an optional ones name. Two small lookup tables cover both patterns. Every nonzero part contributes its name in order, and joining those words with single spaces gives the required phrase.
Algorithm
Return
"zero"immediately when the input is0.When the input is at least
1000, divide by1000. Add the integer quotient's name followed bythousand, then keep the remainder.When the remainder is at least
100, divide by100. Add the integer quotient's name followed byhundred, then keep the remainder.When the remaining number is at least
20, use its tens digit to add the tens word, then keep only the ones digit.When the remaining number is positive, add its name from the table for
1through19.Join the collected words with single spaces and return the string.
Dry Run
Convert Digits/Numbers to Words
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the English words for num. string numberToWords(int num) { // Zero needs its own word because every place would be skipped. if (num == 0) { return "zero"; } // The indices are the full small number and the tens digit. const string small[] = { "", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" }; const string tens[] = { "", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" }; vector<string> words; // Add the thousands phrase only when the thousands digit is present. if (num >= 1000) { words.push_back(small[num / 1000]); words.push_back("thousand"); num %= 1000; } // Add the hundreds phrase only when the hundreds digit is nonzero. if (num >= 100) { words.push_back(small[num / 100]); words.push_back("hundred"); num %= 100; } // Values from twenty onward use a separate tens word. if (num >= 20) { words.push_back(tens[num / 10]); num %= 10; } // A positive remainder has a complete name in the small table. if (num > 0) { words.push_back(small[num]); } string answer = words[0]; // Add a separator before each word after the first. for (size_t i = 1; i < words.size(); i++) { answer += " "; answer += words[i]; } return answer; }};// Driver codeint main() { int num = 4027; // instance for class Solution Solution sol; cout << sol.numberToWords(num) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(1) because the four-digit limit bounds the number of lookups and the length of the joined string.
Space Complexity: O(1) auxiliary space because the lookup tables have fixed sizes and the list holds at most six words.
Interview follow-up Questions
The general rules emit words only for nonzero parts. Every part of 0 is zero, so the special case supplies the word "zero".
Be the first to add a comment.