Convert Digits/Numbers to Words

17
1

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 is 0.

  • When the input is at least 1000, divide by 1000. Add the integer quotient's name followed by thousand, then keep the remainder.

  • When the remainder is at least 100, divide by 100. Add the integer quotient's name followed by hundred, 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 1 through 19.

  • Join the collected words with single spaces and return the string.

Dry Run

Convert Digits/Numbers to Words

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 code
int 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".

MathsStringTCS NQT

Read Similar Blogs

Comments0