273

273. Integer to English Words (Hard)

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"

Example 4:

Input: num = 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

 

Constraints:

• 0 <= num <= 231 - 1

Companies:
Amazon, Facebook, Microsoft, Adobe, Square, Google, LinkedIn, Walmart Labs

Related Topics:
Math, String, Recursion

Similar Questions:

• Integer to Roman (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/integer-to-english-words/
// Author: github.com/lzl124631x
// Time: O(lgN)
// Space: O(lgN)
class Solution {
    const string one[9] = {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    const string teen[10] = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    const string ty[10] = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    const string segments[3] = {"Thousand", "Million", "Billion"};
public:
    string numberToWords(int num) {
        if (num == 0) return "Zero";
        vector<string> ans;
        int segIndex = -1;
        for (; num; num /= 1000) {
            int digits[3] = {}, segment = num % 1000;
            if (segIndex > -1 && segment) ans.push_back(segments[segIndex]);
            ++segIndex;
            for (int i = 0; i < 3 && segment; ++i) {
                digits[i] = segment % 10;
                segment /= 10;
            }
            if (digits[1] != 1 && digits[0]) ans.push_back(one[digits[0] - 1]);
            if (digits[1] == 1) {
                ans.push_back(teen[digits[0]]);
            } else if (digits[1] > 1) {
                ans.push_back(ty[digits[1] - 2]);
            }
            if (digits[2]) {
                ans.push_back("Hundred");
                ans.push_back(one[digits[2] - 1]);
            }
        }
        string merged;
        for (int i = ans.size() - 1; i >= 0; --i) {
            if (merged.size()) merged += " ";
            merged += ans[i];
        }
        return merged;
    }
};