Solving "Integer to English Words" LeetCode problem

I first came across this problem during an online assessment for a job. In this post, I'll revisit it and solve it using TypeScript.

Problem Statement

Taken from the problem description:

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

Constraint: 0 <= num <= 2^31 - 1

This problem asks us to convert a number to its English words representation. The constraint is that num has a maximum value of 2^31 - 1 (2,147,483,647), a positive number.

For example, 123 should be converted to One Hundred Twenty Three and 123456791 should be converted to One Hundred Twenty Three Million Four Hundred Fifty Six Thousand Seven Hundred Ninety One. Sounds easy enough, huh? (Spoiler alert: it's not)

Solution

Step 1. Creating Dictionary

This dictionary maps numbers to their English words. We'll use it to convert numbers.

const translations: Record<number, string> = {
  0: "Zero",
  1: "One",
  2: "Two",
  3: "Three",
  4: "Four",
  5: "Five",
  6: "Six",
  7: "Seven",
  8: "Eight",
  9: "Nine",
  10: "Ten",
  11: "Eleven",
  12: "Twelve",
  13: "Thirteen",
  14: "Fourteen",
  15: "Fifteen",
  16: "Sixteen",
  17: "Seventeen",
  18: "Eighteen",
  19: "Nineteen",
  20: "Twenty",
  30: "Thirty",
  40: "Forty",
  50: "Fifty",
  60: "Sixty",
  70: "Seventy",
  80: "Eighty",
  90: "Ninety",
  100: "Hundred",
  1_000: "Thousand",
  1_000_000: "Million",
  1_000_000_000: "Billion",
}

Notice the Record<number, string>, this is important to tell TypeScript that the keys of this dictionary are numbers and the values are strings. If we omit this, when we try to access the dictionary with a number: translations[1], TypeScript will throw an error:

No index signature with a parameter of type 'number' was found on type { 0: string; 1: string; ... }

This is because TypeScript expects the index signature to be keyof typeof translations. This is one of those roadblocks that I encountered when I first tried to solve this problem. I know, TypeScript can be a double-edged sword.

Step 2. Converting hundreds, tens, and ones

We'll start from the lowest scale component up until 999. We will not touch the thousands and up yet. Create a function named convert like so:

function convert(num: number): string {
  let result = ""

  if (num >= 100) {
    const hundred = Math.floor(num / 100)
    result += ` ${translations[hundred]} Hundred`

    num -= hundred * 100
  }

  if (num > 0) {
    if (num <= 20) {
      result += ` ${translations[num]}`
    } else {
      const ten = Math.floor(num / 10)
      result += ` ${translations[ten * 10]}`

      const one = num % 10
      if (one > 0) {
        result += ` ${translations[one]}`
      }
    }
  }

  return result
}

Let's break down the logic:

1. First, we handle the hundreds (if any). We divide num by 100 and floor it. For example, 123 gives 1. We append "One Hundred" to result.
2. We subtract hundred * 100 from num.
3. If num > 0, and <=20, append the direct translation. Otherwise, append the ten's place (like "Twenty") and then the one's if any.
4. Return the result.

Step 3. Converting billions, millions, and thousands

We've created the convert function for up to 999. Now let's write the main numberToWords function.

function numberToWords(num: number): string {
  if (num === 0) return translations[0]

  let result = ""

  if (num >= 1_000_000_000) {
    const billion = Math.floor(num / 1_000_000_000)
    result += `${convert(billion)} Billion`

    num -= billion * 1_000_000_000
  }

  if (num >= 1_000_000) {
    const million = Math.floor(num / 1_000_000)
    result += `${convert(million)} Million`

    num -= million * 1_000_000
  }

  if (num >= 1_000) {
    const thousand = Math.floor(num / 1_000)
    result += `${convert(thousand)} Thousand`

    num -= thousand * 1_000
  }

  if (num > 0) {
    result += convert(num)
  }

  return result.trim()
}

We use the convert function we just created. We mutate num from billions down to thousands. Since convert handles 3-digit numbers, we use it for each scale.

The full code will look like this.