Solving "Integer to English Words" LeetCode problem
I first came across this problem on an online assessment for a job application. In this post, I will try to to revisit this problem and solve it. I will be using TypeScript for this solution.
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. With constraint that num a has a maximum value of 32-bit signed integer, which is equal to 2.147.483.647 and is 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 a number to its English words representation. We will use this dictionary whenever we need to convert a number.
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:
We are mutating the num
variable until it reaches 0. Let's break down the logic:
- First, we handle the hundreds (if there is any). We divide the
num
by 100 and round it down to the nearest integer withMath.floor
method. For example, ifnum
is 123, we will get 1.23 which will be rounded down to 1. We store this number inhundred
variable. - We then use this number to access the dictionary and concatenate it with the word "Hundred". For example, if
num
is 123, we will get "One Hundred". This get appended to theresult
variable. - We mutate
num
, substracting it withhundred
. After the subtraction, ifnum
is 0, we will return theresult
variable. Otherwise, we will continue to the next step. - Since number 1-20 English words representation is unique (no more combination), we can just access the dictionary with the
num
and append it to theresult
variable. Otherwise, we will do the same thing as we did with the hundreds.
Step 3. Converting billions, millions, and thousands
We had just finished with convert
function that deals with the hundreds, tens, and ones. Now, we will create the actual numberToWords
function.
As you can see, we are using the convert
function that we created in the previous step. We are also mutating the num
variable until it reaches 0, starting from the leftmost scale component (billion) to the right (thousand). Except this time, we are converting the the numbers with the the convert
function since it conveniently handles 3-digit numbers.
The full code will look like this.