0243HardMathStringRecursion

Spell the Voucher Amount

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A payments desk prints vouchers, and each voucher carries its amount spelled out in words beside the figures. Given a non-negative integer amount, return the words the printer should put on the voucher.

The printer's vocabulary is fixed. Single figures and teens: 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. Whole tens: 20 Twenty, 30 Thirty, 40 Forty, 50 Fifty, 60 Sixty, 70 Seventy, 80 Eighty, 90 Ninety. It also holds the words Hundred, Thousand, Million, Billion and Zero.

The printer works to these rules.

An amount of 0 prints as Zero. For every other amount the word Zero is never printed.
Cut the figures into groups of three digits, counting from the right, so the leftmost group may be short. Read from the left, the groups are tagged Billion, Million, Thousand, and the rightmost group carries no tag.
A group whose digits are all 0 prints nothing whatsoever, tag included.
Any other group prints, in this order: the word for its hundreds digit followed by Hundred when that digit is not 0; then the number formed by its last two digits, as one word when that number is 1 through 19, as the whole-tens word plus the units word when the units digit is not 0, as the whole-tens word by itself when the units digit is 0, and as nothing at all when both digits are 0. The group's tag comes last.
Exactly one space separates neighbouring words. No hyphens, no commas, no and, and no space at either end of the answer.

Examples

Example 1

Input: amount = 907
Output: "Nine Hundred Seven"

There is one group, 907. Its hundreds digit is 9, which prints Nine Hundred, and its last two digits form 7, which prints Seven.

Example 2

Input: amount = 6042519
Output: "Six Million Forty Two Thousand Five Hundred Nineteen"

The groups are 6, 042 and 519, tagged Million, Thousand and nothing. They print Six Million, then Forty Two Thousand, then Five Hundred Nineteen.

Example 3

Input: amount = 5000018
Output: "Five Million Eighteen"

The groups are 5, 000 and 018. The middle group is all zeros, so it prints nothing and its Thousand tag goes with it, leaving Five Million Eighteen.

Constraints

0 <= amount <= 2^31 - 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def spell_amount(amount: int) -> str:

Java

public String spellAmount(int amount)

The intended approach

Time O(d), where d is the number of digits in amount, at most 10 under the stated boundSpace O(d) for the collected word list and the returned string

Repeated division by 1000 peels the amount into its three-digit groups, and a group's position in that list is exactly its tag index, so no digit counting is needed. A helper spells one group in the range 1 to 999 by recursion on three cases: under twenty is a single word, under one hundred is the whole-tens word followed by whatever the units digit spells, and anything larger is a digit word plus `Hundred` followed by whatever the last two digits spell. The groups are then emitted from the most significant down, with a zero group skipped so its tag is skipped with it, and the collected words are joined by single spaces. The recursion never goes deeper than three calls. The amount `0` is answered before any of this, since it is the only case that prints `Zero`.

Pythonentry point: spell_amount

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


def spell_amount(amount):
    if amount == 0:
        return "Zero"

    def spell_group(value):
        if value == 0:
            return []
        if value < 20:
            return [SMALL_WORDS[value]]
        if value < 100:
            return [TENS_WORDS[value // 10]] + spell_group(value % 10)
        return [SMALL_WORDS[value // 100], "Hundred"] + spell_group(value % 100)

    groups = []
    rest = amount
    while rest:
        groups.append(rest % 1000)
        rest //= 1000
    words = []
    for index in range(len(groups) - 1, -1, -1):
        if groups[index]:
            words.extend(spell_group(groups[index]))
            if index:
                words.append(SCALE_WORDS[index])
    return " ".join(words)

The obvious version

Pad the figures to twelve digits as text, walk the four groups left to right, and pick the hundreds, tens and units words out of plain lookup tables with the teens handled as their own branch. No recursion. O(1) for the fixed twelve digits.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_spell_amount(amount):
    if amount == 0:
        return "Zero"
    units = {1: "One", 2: "Two", 3: "Three", 4: "Four", 5: "Five", 6: "Six",
             7: "Seven", 8: "Eight", 9: "Nine"}
    teens = {0: "Ten", 1: "Eleven", 2: "Twelve", 3: "Thirteen", 4: "Fourteen",
             5: "Fifteen", 6: "Sixteen", 7: "Seventeen", 8: "Eighteen",
             9: "Nineteen"}
    tens = {2: "Twenty", 3: "Thirty", 4: "Forty", 5: "Fifty", 6: "Sixty",
            7: "Seventy", 8: "Eighty", 9: "Ninety"}
    digits = str(amount).rjust(12, "0")
    scales = ["Billion", "Million", "Thousand", ""]
    pieces = []
    for slot in range(4):
        trio = digits[slot * 3:slot * 3 + 3]
        if trio == "000":
            continue
        hundreds = int(trio[0])
        tens_digit = int(trio[1])
        unit_digit = int(trio[2])
        if hundreds:
            pieces.append(units[hundreds])
            pieces.append("Hundred")
        if tens_digit == 1:
            pieces.append(teens[unit_digit])
        else:
            if tens_digit >= 2:
                pieces.append(tens[tens_digit])
            if unit_digit:
                pieces.append(units[unit_digit])
        if scales[slot]:
            pieces.append(scales[slot])
    return " ".join(pieces)

How this problem was checked

Reference solution executed against 20 test cases — 20 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in