// 演算法：把 13 個「值 → 羅馬符號」候選由大到小排好，每次扣掉能放的最大值並把符號接到答案後面。
// Algorithm: list 13 (value, symbol) candidates largest-first; greedily subtract the biggest
// value that fits into num and append its symbol to the answer until num reaches 0.

#include <stdlib.h>   // malloc / 動態配置記憶體 / for dynamic memory allocation
#include <string.h>   // strcpy / 字串複製 / for copying C-strings

char* intToRoman(int num) {
    // 平行陣列：values[i] 對應 symbols[i] / Parallel arrays: values[i] pairs with symbols[i].
    // 從大到小排好，這是貪心法的關鍵 / Sorted largest-first — required for the greedy loop.
    int values[13]      = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    const char* symbols[13] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

    // 最壞情況 3999 = MMMCMXCIX，長度 15；給 20 個字元的緩衝足夠且簡單 / Worst-case length
    // is 15 (for 3999); 20 bytes is a safe, simple upper bound including the '\0' terminator.
    char* result = (char*)malloc(20 * sizeof(char));
    // malloc 不會清零，先把第一個位元組設成 '\0' 形成空字串 / malloc doesn't zero memory,
    // so we set the first byte to '\0' to make result a valid empty C-string.
    result[0] = '\0';
    // len 追蹤目前已寫入的長度，避免每次都用 strlen 重新掃描 / len tracks current length so
    // we don't pay O(length) for strlen on every append.
    int len = 0;

    // 遍歷 13 個候選，從大到小 / Iterate through all 13 candidates, largest to smallest.
    for (int i = 0; i < 13; i++) {
        // 當前候選值還能扣就一直扣 / Subtract this value while it still fits — e.g. 3000
        // produces three 'M' appends before moving on.
        while (num >= values[i]) {
            // 把符號字串複製到 result 結尾 / Copy this symbol onto the end of result.
            // strcpy 會自動寫入結尾的 '\0' / strcpy also writes the trailing '\0'.
            strcpy(result + len, symbols[i]);
            // 更新長度：加上剛複製字串的長度 / Advance len by the length of the symbol we
            // just copied (1 for base symbols, 2 for subtractive pairs).
            len += (int)strlen(symbols[i]);
            // 從 num 扣掉這個值 / Subtract the value from num so the loop makes progress.
            num -= values[i];
        }
    }

    // LeetCode 會在使用後 free() 這塊記憶體，所以直接回傳即可 / LeetCode's harness frees
    // the returned pointer, so we just return it.
    return result;
}