Integer to English Words

Leetcode Problem:

• Integer to English Words

Summary

• Convert a non-negative integer to its English words representation.

Approach

• The approach used is to recursively break down the number into smaller parts (thousands, millions, billions) and then convert each part to words using a combination of arrays and helper functions.

Complexity

• O(log n) where n is the number of digits in the input number

Explain

• The solution code uses three arrays to store the words for thousands, millions, and billions
• It also uses a helper function `getUnderHndred` to convert numbers less than 100 to words
• The `numberToWords` function recursively breaks down the input number into smaller parts and then combines the words for each part to form the final result.

Solution Code:

class Solution {
public:
    string digitOf1000[5] = {
        "",
        " Thousand",
        " Million",
        " Billion"

    };
    string digitOf10[11] = {
        "",
        " Ten",
        " Twenty",
        " Thirty",
        " Forty",
        " Fifty",
        " Sixty",
        " Seventy",
        " Eighty",
        " Ninety"
    };
    string underTwenty[21] = {
        "",
        " One",
        " Two",
        " Three",
        " Four",
        " Five",
        " Six",
        " Seven",
        " Eight",
        " Nine",
        " Ten",
        " Eleven",
        " Twelve",
        " Thirteen",
        " Fourteen",
        " Fifteen",
        " Sixteen",
        " Seventeen",
        " Eighteen",
        " Nineteen"
    };
    string getUnderHndred(int num){
        if (num < 20){
            return underTwenty[num];
        }
        string s = "";
        if (num / 10 > 0){
            s += digitOf10[num/10];
        }
        if (num %10 > 0){
            s += underTwenty[num % 10];
        }
        return s;
    }

    string numberToWords(int num) {
        string res = "";
        int cnt = 0;
        if (num == 0) return "Zero";
        while(num){
            string s = "";
            int num2 = (num % 1000);
            if ( num2 / 100){
                s += underTwenty[num2/100] + " Hundred";
            }
            s += getUnderHndred(num2 % 100);
            if (s.compare("") != 0)
                res = s + digitOf1000[cnt] + res;
            num /= 1000;
            cnt++;
        }
        return res.substr(1);
    }
};