Show problems as
Classic problem #12MediumHash TableMathString

Integer to Roman

Real-world version: Vault Stroke Code
Tracked in this browser only
Read Integer to Roman on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A vault labels every crate with a stroke code, a numeral written from seven marks:

markvalue
A1
E5
G10
N50
R100
W500
Z1000

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:

pairvalue
AE4
AG9
GN40
GR90
RW400
RZ900

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def stroke_code(amount: int) -> str:
Java
public String strokeCode(int amount)

More on the same topics