0042MediumHash TableMathString

Vault Stroke Code

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 vault labels every crate with a stroke code, a numeral written from seven marks:

mark	value
`A`	1
`E`	5
`G`	10
`N`	50
`R`	100
`W`	500
`Z`	1000

A code is read left to right and its marks are added up, and clerks normally write the values in falling order, so NGGEA stands for 50 + 10 + 10 + 5 + 1 = 76.

To keep a mark from appearing four times in a row, six pairs may instead be written with the smaller mark in front of the larger one, which means subtract rather than add:

pair	value
`AE`	4
`AG`	9
`GN`	40
`GR`	90
`RW`	400
`RZ`	900

Given a positive integer amount, return the stroke code for it that uses the fewest marks. Exactly one code of that length exists for each amount in range.

Examples

Example 1

Input: amount = 2076
Output: "ZZNGGEA"

2076 = 1000 + 1000 + 50 + 10 + 10 + 5 + 1, and no subtractive pair applies.

Example 2

Input: amount = 1215
Output: "ZRRGE"

1215 = 1000 + 100 + 100 + 10 + 5, so a thousand mark, two hundred marks, a ten mark and a five mark.

Example 3

Input: amount = 1946
Output: "ZRZGNEA"

1946 = 1000 + 900 + 40 + 5 + 1, where 900 is the pair RZ and 40 is the pair GN.

Constraints

1 <= amount <= 3999

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 stroke_code(amount: int) -> str:

Java

public String strokeCode(int amount)

The intended approach

Time O(1) - the table holds thirteen entries and at most fifteen marks are emittedSpace O(1) beyond the returned code

List the thirteen writable pieces, the seven single marks plus the six subtractive pairs, in falling value order. Walk that list once and, while the piece still fits inside what is left of the amount, append it and subtract its value. Taking the largest piece that fits is safe because no run of smaller pieces is ever shorter than the piece it replaces.

Pythonentry point: stroke_code

def stroke_code(amount):
    pieces = ((1000, "Z"), (900, "RZ"), (500, "W"), (400, "RW"), (100, "R"),
              (90, "GR"), (50, "N"), (40, "GN"), (10, "G"), (9, "AG"),
              (5, "E"), (4, "AE"), (1, "A"))
    out = []
    for value, mark in pieces:
        while amount >= value:
            out.append(mark)
            amount -= value
    return "".join(out)

The obvious version

Table lookup per decimal digit instead of a greedy sweep: spell out all ten codes for the units place, the tens place and the hundreds place, plus the four for the thousands place, then split the amount into digits and glue the four pieces together.

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_stroke_code(amount):
    ones = ["", "A", "AA", "AAA", "AE", "E", "EA", "EAA", "EAAA", "AG"]
    tens = ["", "G", "GG", "GGG", "GN", "N", "NG", "NGG", "NGGG", "GR"]
    hundreds = ["", "R", "RR", "RRR", "RW", "W", "WR", "WRR", "WRRR", "RZ"]
    thousands = ["", "Z", "ZZ", "ZZZ"]
    return (thousands[amount // 1000]
            + hundreds[amount // 100 % 10]
            + tens[amount // 10 % 10]
            + ones[amount % 10])

How this problem was checked

Reference solution executed against 14 test cases — 14 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