Jobs

Interviews

Discussions

Integer to English Words

Hard

Roblox

2 views

Topics:

ArraysStringsRecursion

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

Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"

Example 2:

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

Example 3:

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

Constraints:

0 <= num <= 2³¹ - 1

Integer to English Words

Hard

Roblox

2 views

Topics:

ArraysStringsRecursion

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

Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"

Example 2:

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

Example 3:

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

Constraints:

0 <= num <= 2³¹ - 1

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input integer `num`? Is there a maximum possible value?
Should I handle the case where the input integer is zero?
Are there any specific formatting requirements for the output string, such as capitalization or spacing?
How should I handle potentially large numbers that require words like 'billion' or 'trillion'?
If the input is invalid (e.g., negative, or outside the specified range), what should my function return? Should I throw an error, or return a specific string like 'Invalid Input'?

Brute Force Solution

Approach

The brute force strategy for converting a number to English words involves checking every possible combination of number groupings. We look at each digit place and decide what English word or phrase represents it. By checking all possibilities, we piece together the full English phrase.

Here's how the algorithm would work step-by-step:

First, handle the special case if the number is zero and return 'Zero'.
Break the number into groups based on place value, such as billions, millions, thousands, and ones.
For each group, figure out how to translate it into English words.
Within each group, handle hundreds, tens, and ones places individually.
For numbers less than 20, look up their direct English word representation (e.g., 1 is 'One', 12 is 'Twelve').
For tens places, combine the correct tens word (e.g., 'Twenty', 'Thirty') with the ones place word.
For the hundreds place, add 'Hundred' after the digit (e.g., 'Two Hundred').
After translating each group, add the corresponding place value word (e.g., 'Thousand', 'Million', 'Billion').
Put all the English words for each group together in the correct order to build the final phrase.
Check every possible combination and correct any spacing issues (e.g., extra spaces) to give the final valid result.

Code Implementation

def integer_to_english(number):
    if number == 0:
        return 'Zero'

    less_than_20 = ['','One','Two','Three','Four','Five','Six','Seven','Eight','Nine','Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']
    tens = ['','','Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']
    thousands = ['','Thousand','Million','Billion']

    def helper(number):
        if number < 20:
            return less_than_20[number]
        elif number < 100:
            return tens[number // 10] + (' ' + less_than_20[number % 10])
        else:
            return less_than_20[number // 100] + ' Hundred ' + helper(number % 100)

    result = []
    # Iterate through the place values
    for i in range(4):
        number_to_process = number % 1000

        if number_to_process != 0:
            # Translate the group into english words
            result.append(helper(number_to_process) + ' ' + thousands[i])
        number //= 1000

    # Reverse the order and join the words
    return ' '.join(result[::-1]).strip()

Big(O) Analysis

Time Complexity

O(1) – The input number is at most a 32-bit integer, meaning the maximum number of digits is fixed (10). The described algorithm involves breaking the number into groups (billions, millions, thousands, ones) and processing each group, which involves a fixed number of operations regardless of the specific input value. Since the number of operations is bounded by a constant and does not depend on a variable input size, the time complexity is O(1).

Space Complexity

O(1) – The algorithm primarily uses constant space. It stores a few string literals for numbers (e.g., 'One', 'Twelve', 'Hundred', 'Thousand', 'Million', 'Billion') and a handful of integer variables to track place values. The space used for these variables and constants does not depend on the size of the input number N; therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

To convert a number to English words, we break it down into chunks based on powers of 1000 (billions, millions, thousands, ones). We then convert each chunk into words and combine them with the appropriate magnitude word.

Here's how the algorithm would work step-by-step:

First, handle the special case when the input number is zero.
Create lists of words for single digits, teens, tens, and magnitude words (thousand, million, billion).
Break the input number into groups of three digits from right to left. Each group represents a power of 1000.
Process each three-digit group. Convert the hundreds digit to words (e.g., 'two hundred').
Convert the tens and ones digits to words. Handle cases like numbers between 10-19 specially.
Combine the hundreds, tens, and ones words for the current group.
If the group is not zero, add the appropriate magnitude word (thousand, million, billion) to the end of the group's words.
Combine the words from each group, starting with the largest magnitude and working down to the smallest.
Remove any unnecessary spaces in the final result.

Code Implementation

def integer_to_english(number):
    if number == 0:
        return "Zero"

    ones = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
    teens = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
    tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
    thousands = ["", "Thousand", "Million", "Billion"]

    def convert_group_to_words(num):
        if num == 0:
            return ""

        hundreds_place = num // 100
        remainder = num % 100
        words = ""

        if hundreds_place:
            words += ones[hundreds_place] + " Hundred "

        if remainder < 10:
            words += ones[remainder]
        elif remainder < 20:
            words += teens[remainder - 10]
        else:
            words += tens[remainder // 10] + " " + ones[remainder % 10]

        return words.strip()

    result = ""
    group_index = 0

    # Process groups of three digits
    while number > 0:
        current_number_group = number % 1000
        number //= 1000

        # Convert the group to English words
        group_words = convert_group_to_words(current_number_group)

        # Add the magnitude word if the group is not zero
        if group_words:
            result = group_words + " " + thousands[group_index] + " " + result

        group_index += 1

    # Remove extra spaces and return the result
    return result.strip()

Big(O) Analysis

Time Complexity

–

Space Complexity

O(1) – The algorithm utilizes a fixed number of string arrays to store the English word representations of digits, teens, tens, and magnitudes. The size of these arrays is constant and independent of the input number N. The space used to construct the final English word string is not considered auxiliary space, because it is considered to be the output of the algorithm. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input is 0	Return 'Zero' directly as it's a base case.
Input is a negative number	Handle negative numbers by checking if num < 0 and returning an error string or throwing an exception, as the problem specifies a non-negative integer.
Input exceeds the maximum integer value (Integer.MAX_VALUE)	The problem states the input is an integer, but we can handle by checking if the input is larger than Integer.MAX_VALUE and return an error or handle as needed.
Input is a number in the thousands, millions, or billions range with trailing zeros (e.g., 1000, 1000000, 1000000000)	Ensure correct handling of trailing zeros by properly concatenating thousands, millions, and billions appropriately.
Input contains only a few significant digits followed by many zeros (e.g., 100000, 20000000)	Correctly handle numbers with multiple trailing zeros by processing digit groups based on magnitude (thousands, millions, etc.).
Numbers close to the boundaries of thousands, millions, billions (e.g., 999, 999999, 999999999)	Handle transition between different magnitude groups (hundreds to thousands, thousands to millions) correctly.
Numbers with consecutive zeros (e.g., 1001, 1000010)	Bypass zero values and only consider significant digits during conversion.
Maximum integer value (2147483647)	Ensure the solution correctly converts the maximum 32-bit integer value to its English word representation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input integer `num`? Is there a maximum possible value?
Should I handle the case where the input integer is zero?
Are there any specific formatting requirements for the output string, such as capitalization or spacing?
How should I handle potentially large numbers that require words like 'billion' or 'trillion'?
If the input is invalid (e.g., negative, or outside the specified range), what should my function return? Should I throw an error, or return a specific string like 'Invalid Input'?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, handle the special case if the number is zero and return 'Zero'.
Break the number into groups based on place value, such as billions, millions, thousands, and ones.
For each group, figure out how to translate it into English words.
Within each group, handle hundreds, tens, and ones places individually.
For numbers less than 20, look up their direct English word representation (e.g., 1 is 'One', 12 is 'Twelve').
For tens places, combine the correct tens word (e.g., 'Twenty', 'Thirty') with the ones place word.
For the hundreds place, add 'Hundred' after the digit (e.g., 'Two Hundred').
After translating each group, add the corresponding place value word (e.g., 'Thousand', 'Million', 'Billion').
Put all the English words for each group together in the correct order to build the final phrase.
Check every possible combination and correct any spacing issues (e.g., extra spaces) to give the final valid result.

Code Implementation

def integer_to_english(number):
    if number == 0:
        return 'Zero'

    less_than_20 = ['','One','Two','Three','Four','Five','Six','Seven','Eight','Nine','Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']
    tens = ['','','Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']
    thousands = ['','Thousand','Million','Billion']

    def helper(number):
        if number < 20:
            return less_than_20[number]
        elif number < 100:
            return tens[number // 10] + (' ' + less_than_20[number % 10])
        else:
            return less_than_20[number // 100] + ' Hundred ' + helper(number % 100)

    result = []
    # Iterate through the place values
    for i in range(4):
        number_to_process = number % 1000

        if number_to_process != 0:
            # Translate the group into english words
            result.append(helper(number_to_process) + ' ' + thousands[i])
        number //= 1000

    # Reverse the order and join the words
    return ' '.join(result[::-1]).strip()

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, handle the special case when the input number is zero.
Create lists of words for single digits, teens, tens, and magnitude words (thousand, million, billion).
Break the input number into groups of three digits from right to left. Each group represents a power of 1000.
Process each three-digit group. Convert the hundreds digit to words (e.g., 'two hundred').
Convert the tens and ones digits to words. Handle cases like numbers between 10-19 specially.
Combine the hundreds, tens, and ones words for the current group.
If the group is not zero, add the appropriate magnitude word (thousand, million, billion) to the end of the group's words.
Combine the words from each group, starting with the largest magnitude and working down to the smallest.
Remove any unnecessary spaces in the final result.

Code Implementation

def integer_to_english(number):
    if number == 0:
        return "Zero"

    ones = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
    teens = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
    tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
    thousands = ["", "Thousand", "Million", "Billion"]

    def convert_group_to_words(num):
        if num == 0:
            return ""

        hundreds_place = num // 100
        remainder = num % 100
        words = ""

        if hundreds_place:
            words += ones[hundreds_place] + " Hundred "

        if remainder < 10:
            words += ones[remainder]
        elif remainder < 20:
            words += teens[remainder - 10]
        else:
            words += tens[remainder // 10] + " " + ones[remainder % 10]

        return words.strip()

    result = ""
    group_index = 0

    # Process groups of three digits
    while number > 0:
        current_number_group = number % 1000
        number //= 1000

        # Convert the group to English words
        group_words = convert_group_to_words(current_number_group)

        # Add the magnitude word if the group is not zero
        if group_words:
            result = group_words + " " + thousands[group_index] + " " + result

        group_index += 1

    # Remove extra spaces and return the result
    return result.strip()

Big(O) Analysis

Time Complexity

–

Space Complexity

Edge Cases

Case	How to Handle
Input is 0	Return 'Zero' directly as it's a base case.
Input is a negative number	Handle negative numbers by checking if num < 0 and returning an error string or throwing an exception, as the problem specifies a non-negative integer.
Input exceeds the maximum integer value (Integer.MAX_VALUE)	The problem states the input is an integer, but we can handle by checking if the input is larger than Integer.MAX_VALUE and return an error or handle as needed.
Input is a number in the thousands, millions, or billions range with trailing zeros (e.g., 1000, 1000000, 1000000000)	Ensure correct handling of trailing zeros by properly concatenating thousands, millions, and billions appropriately.
Input contains only a few significant digits followed by many zeros (e.g., 100000, 20000000)	Correctly handle numbers with multiple trailing zeros by processing digit groups based on magnitude (thousands, millions, etc.).
Numbers close to the boundaries of thousands, millions, billions (e.g., 999, 999999, 999999999)	Handle transition between different magnitude groups (hundreds to thousands, thousands to millions) correctly.
Numbers with consecutive zeros (e.g., 1001, 1000010)	Bypass zero values and only consider significant digits during conversion.
Maximum integer value (2147483647)	Ensure the solution correctly converts the maximum 32-bit integer value to its English word representation.