Pattern visualizer
Integer to Roman
Roman numerals look like a special-case nightmare — sometimes letters add, sometimes one letter subtracts from the next — until you notice that the six subtractive forms (CM, CD, XC, XL, IX, IV) can just be listed as values of their own. Put all thirteen values in one descending table and the rule collapses to: repeatedly take the largest value that still fits and write its symbol. Because 900 and 40 are entries, the greedy choice can never produce an illegal run of four identical letters. The input is capped at 3999, so the loop runs a bounded number of times no matter the value — this is O(1) in both time and space. Animated on: num = 3749 — write it as a Roman numeral..
Greedy over a descending table that already holds the subtractive pairs
num = 3749, output empty. The table is scanned high to low: 1000, 900, 500, 400, ... down to 1. The six subtractive forms (CM, CD, XC, XL, IX, IV) sit IN that table as ordinary entries, which is what stops the greedy pass from ever writing four of the same letter in a row — 40 is reachable directly, so XXXX is never the largest thing that fits.
1FUNCTION intToRoman(num)2 VALUES <- [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]3 SYMBOLS <- [M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I]4 out <- EMPTY5 FOR i <- 0 TO LENGTH(VALUES) - 16 WHILE num >= VALUES[i]7 APPEND SYMBOLS[i] TO out8 num <- num - VALUES[i]9 RETURN out
← / → step · space play · Home restart