#273

Hard

LeetCode Problem Workspace

Integer to English Words

Convert a given integer to its English words representation using mathematical logic and string manipulation.

Problem Statement

Given a non-negative integer, convert it to its English words representation. The number is divided into manageable chunks, like thousands, millions, and billions, which need to be converted individually into English words and combined correctly. Special attention must be given to numbers like 0, 100, and the hyphenated 'and' used in certain cases in English phrasing.

For example, 123 becomes 'One Hundred Twenty Three', and 12345 becomes 'Twelve Thousand Three Hundred Forty Five'. The solution must consider edge cases such as numbers between 0 and 19, and it should handle up to the largest possible input value of 2,147,483,647.

Examples

Example 1

Input: num = 123

Output: "One Hundred Twenty Three"

Example details omitted.

Example 2

Input: num = 12345

Output: "Twelve Thousand Three Hundred Forty Five"

Example details omitted.

Example 3

Input: num = 1234567

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

Example details omitted.

Constraints

0 <= num <= 231 - 1

Solution Approach

Divide and Conquer

Break the integer into chunks representing different magnitude groups (thousands, millions, etc.). Each chunk can be handled separately using a recursive approach.

Word Mapping

Use arrays or dictionaries to map numbers to their English equivalents, especially for smaller numbers (0-19) and powers of ten (hundred, thousand, million).

Edge Case Handling

Ensure proper handling of edge cases, such as zero, and special formatting for numbers like 100, which may need 'and' inserted in the English representation.

Complexity Analysis

Metric	Value
Time	O(K)
Space	O(\log_{10} N)

The time complexity is O(K), where K is the number of digits in the number. The space complexity is O(log₁₀ N) because the number is broken into logarithmic-sized chunks for processing.

What Interviewers Usually Probe

Assess if the candidate can handle large numbers effectively by breaking them into manageable chunks.
Evaluate if the candidate understands how to handle special cases, like 0 or numbers involving 'and'.
Look for clarity in the recursive approach and their ability to manage different word mappings.

Common Pitfalls or Variants

Common pitfalls

Failing to account for edge cases such as zero or numbers that require 'and' in their English phrasing.
Overcomplicating the problem with unnecessary recursion or overly complex data structures.
Misplacing word mappings, particularly for numbers between 10 and 19, or for powers of ten.

Follow-up variants

Convert to words in a different language or format, expanding the scope of number representation.
Implement a version without recursion, relying only on iterative or loop-based solutions.
Extend the problem to handle floating-point numbers or decimals in the conversion.

FAQ

How can I efficiently convert an integer to English words?

Break the number into manageable chunks representing thousands, millions, and billions, then recursively map these chunks to their English equivalents.

What are common pitfalls when solving this problem?

Common issues include mishandling edge cases, using overly complex approaches, or incorrectly mapping numbers in specific ranges like 10-19.

What is the time complexity of the Integer to English Words problem?

The time complexity is O(K), where K is the number of digits in the number, because each digit is processed once.

What edge cases should I be aware of when converting integers to English?

Ensure you handle 0, numbers between 10 and 19, and numbers like 100, which require special formatting (e.g., 'and').

Can the solution handle very large integers, like 2,147,483,647?

Yes, the solution can handle integers up to the maximum value of 2,147,483,647 by breaking the number into chunks representing millions, thousands, etc.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

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', '']

        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)

        res = []
        i, j = 1000000000, 0
        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()

Continue Practicing

#241 different ways to add parentheses #224 basic calculator #770 basic calculator iv