Question

Formatted question description: https://leetcode.ca/all/273.html

 273	Integer to English Words

 Convert a non-negative integer to its english words representation.
 Given input is guaranteed to be less than 2^31 - 1.

 Example 1:

 Input: 123
 Output: "One Hundred Twenty Three"

 Example 2:

 Input: 12345
 Output: "Twelve Thousand Three Hundred Forty Five"

 Example 3:

 Input: 1234567
 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

 Example 4:

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

Algorithm

The highest can only reach billions, and a group of 3 can only handle 4 groups.

Then we need some function to process three groups of numbers

We need to list all English words from 1 to 19 and put them in an array
Also list the English words from 20, 30,… to 90 in another array,

Then, a three-digit n, the hundreds digit is expressed as n/100, the last two digits together are expressed as n%100, the tens digit is expressed as n%100/10, and the single digit is expressed as n%10

Then we see if the last two digits are less than 20

If it is less than, take the word directly from the array
If it is greater than or equal to 20, then take the ten and one digit words from the two arrays respectively

Then deal with the number on the hundreds, and remember to add Hundred.

Call this helper function four times in the main function, then insert “Thousand”, “Million”, “Billion” in the middle to the corresponding position, and finally check whether there are spaces at the end, delete all spaces, and check the input when returning whether it is 0, if yes, return ‘Zero’.

Code

import java.util.Arrays;
import java.util.List;

public class Integer_to_English_Words {

    public static void main(String[] args) {
        Integer_to_English_Words out = new Integer_to_English_Words();
        Solution s = out.new Solution();

        System.out.println(s.numberToWords(123));
        System.out.println(s.numberToWords(1234567891));
    }


    class Solution {

        List<String> v1 = Arrays.asList("", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen");
        List<String> v2 = Arrays.asList("", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety");

        public String numberToWords(int num) {

            String res = convertHundred(num % 1000);
            List<String> unit = Arrays.asList("Thousand", "Million", "Billion", "Trillion");
            for (int i = 0; i < 3; ++i) {
                num /= 1000;
                res = num % 1000 != 0 ? convertHundred(num % 1000) + " " + unit.get(i) + " " + res : res;
            }

            res = res.trim();

            return res.isEmpty() ? "Zero" : res;
        }

        String convertHundred(int num) {

            String res;
            int a = num / 100, b = num % 100, c = num % 10;

            res = b < 20 ?
                    v1.get(b)
                    : v2.get(b / 10) + (c != 0 ? " " + v1.get(c) : "");
            if (a > 0) {
                res = v1.get(a) + " Hundred" + (b != 0 ? " " + res : "");
            }

            return res;
        }
    }
}

############

class Solution {
    private static Map<Integer, String> map;

    static {
        map = new HashMap<>();
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");
        map.put(5, "Five");
        map.put(6, "Six");
        map.put(7, "Seven");
        map.put(8, "Eight");
        map.put(9, "Nine");
        map.put(10, "Ten");
        map.put(11, "Eleven");
        map.put(12, "Twelve");
        map.put(13, "Thirteen");
        map.put(14, "Fourteen");
        map.put(15, "Fifteen");
        map.put(16, "Sixteen");
        map.put(17, "Seventeen");
        map.put(18, "Eighteen");
        map.put(19, "Nineteen");
        map.put(20, "Twenty");
        map.put(30, "Thirty");
        map.put(40, "Forty");
        map.put(50, "Fifty");
        map.put(60, "Sixty");
        map.put(70, "Seventy");
        map.put(80, "Eighty");
        map.put(90, "Ninety");
        map.put(100, "Hundred");
        map.put(1000, "Thousand");
        map.put(1000000, "Million");
        map.put(1000000000, "Billion");
    }

    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1000000000; i >= 1000; i /= 1000) {
            if (num >= i) {
                sb.append(get3Digits(num / i)).append(' ').append(map.get(i));
                num %= i;
            }
        }
        if (num > 0) {
            sb.append(get3Digits(num));
        }
        return sb.substring(1);
    }

    private String get3Digits(int num) {
        StringBuilder sb = new StringBuilder();
        if (num >= 100) {
            sb.append(' ').append(map.get(num / 100)).append(' ').append(map.get(100));
            num %= 100;
        }
        if (num > 0) {
            if (num < 20 || num % 10 == 0) {
                sb.append(' ').append(map.get(num));
            } else {
                sb.append(' ').append(map.get(num / 10 * 10)).append(' ').append(map.get(num % 10));
            }
        }
        return sb.toString();
    }
}

// OJ: https://leetcode.com/problems/integer-to-english-words/
// 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;
    }
};

'''
In Python 3. x and latest 2. x, floor division for both integer arguments and floating-point arguments is achieved by using the double slash ("//") operator

>>> print(0.6/0.2)
3.0
>>> print(0.6//0.2)
2.0


>>> 3.0 / 2.0
1.5
>>>
>>> 3.0 // 2.0
1.0
'''
class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return 'Zero'

        lt20 = [
            '',
            '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',
        ]
        thousands = ['Billion', 'Million', 'Thousand', ''] # reversed order

        def transfer(num):
            if num == 0:
                return ''
            if num < 20:
                return lt20[num] + ' '
            if num < 100:
                return tens[num // 10] + ' ' + transfer(num % 10)
            return lt20[num // 100] + ' Hundred ' + transfer(num % 100) # 100-999

        res = []
        i, j = 1000000000, 0 # i is 1 billion, j is index of thousands[] list
        while i > 0:
            if num // i != 0:
                res.append(transfer(num // i))
                res.append(thousands[j])
                res.append(' ')
                num %= i
            j += 1
            i //= 1000
        return ''.join(res).strip()

############

units = {1: "", 100: " Hundred", 1000: " Thousand", 1000000: " Million", 1000000000: " Billion"}
tenToTwenty = {10: "Ten", 11: "Eleven", 12: "Twelve", 13: "Thirteen", 14: "Fourteen", 15: "Fifteen", 16: "Sixteen",
               17: "Seventeen", 18: "Eighteen", 19: "Nineteen", 20: "Twenty"}
tens = {2: "Twenty", 3: "Thirty", 4: "Forty", 5: "Fifty", 6: "Sixty", 7: "Seventy", 8: "Eighty", 9: "Ninety"}
digit = {1: "One", 2: "Two", 3: "Three", 4: "Four", 5: "Five", 6: "Six", 7: "Seven", 8: "Eight", 9: "Nine", 10: "Ten"}


class Solution(object):
  def numberToWords(self, num):
    """
    :type num: int
    :rtype: str
    """
    global units, tenToTwenty, tens, digit
    ans = []

    def getNum(number):
      global units, tenToTwenty, tens, digit
      divider = 1000
      ans = []
      h = number / 100
      if h != 0:
        ans.append(digit[h] + " Hundred")
      number = number % 100
      if number in tenToTwenty:
        ans.append(tenToTwenty[number])
      else:
        t = number / 10
        if t != 0:
          ans.append(tens[t])
        number = number % 10
        d = number
        if d != 0:
          ans.append(digit[d])
      return " ".join(ans)

    divider = 1000000000
    while num > 0:
      res = num / divider
      if res != 0:
        ans.append(getNum(res) + units[divider])
      num = num % divider
      divider /= 1000
    if not ans:
      return "Zero"
    return " ".join(ans)

using System.Collections.Generic;
using System.Linq;

public class Solution {
    private string[] bases = { "Thousand", "Million", "Billion" };
    public string NumberToWords(int num) {
        if (num == 0)
        {
            return "Zero";
        }
        var baseIndex = -1;
        var parts = new List<string>();
        while (num > 0)
        {
            var part = NumberToWordsInternal(num % 1000);
            if (part.Length > 0 && baseIndex >= 0)
            {
                part = JoinParts(part, bases[baseIndex]);
            }
            parts.Add(part);
            baseIndex++;
            num /= 1000;
        }
        parts.Reverse();
        return JoinParts(parts);
    }

    private string JoinParts(IEnumerable<string> parts)
    {
        return string.Join(" ", parts.Where(p => p.Length > 0));
    }

    private string JoinParts(params string[] parts)
    {
        return JoinParts((IEnumerable<string>)parts);
    }

    private string NumberToWordsInternal(int num)
    {
        switch(num)
        {
            case 0: return "";
            case 1: return "One";
            case 2: return "Two";
            case 3: return "Three";
            case 4: return "Four";
            case 5: return "Five";
            case 6: return "Six";
            case 7: return "Seven";
            case 8: return "Eight";
            case 9: return "Nine";
            case 10: return "Ten";
            case 11: return "Eleven";
            case 12: return "Twelve";
            case 13: return "Thirteen";
            case 14: return "Fourteen";
            case 15: return "Fifteen";
            case 16: return "Sixteen";
            case 17: return "Seventeen";
            case 18: return "Eighteen";
            case 19: return "Nineteen";
        }

        if (num < 100)
        {
            string part1;
            switch (num/10)
            {
                case 2: part1 = "Twenty"; break;
                case 3: part1 = "Thirty"; break;
                case 4: part1 = "Forty"; break;
                case 5: part1 = "Fifty"; break;
                case 6: part1 = "Sixty"; break;
                case 7: part1 = "Seventy"; break;
                case 8: part1 = "Eighty"; break;
                case 9: default: part1 = "Ninety"; break;
            }
            var part2 = NumberToWordsInternal(num % 10);
            return JoinParts(part1, part2);
        }

        {
            var part1 = NumberToWordsInternal(num / 100);
            var part2 = NumberToWordsInternal(num % 100);
            return JoinParts(part1, "Hundred", part2);
        }
    }
}

273 - Integer to English Words

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions