2553. Separate the Digits in an Array

題目 / Problem

中文： 給定一個正整數陣列 nums，請依照原本的順序，把每個整數的數字「逐位拆開」後串成一個新的陣列回傳。例如 10921 拆開後是 [1,0,9,2,1]。

English: Given an array of positive integers nums, return an array answer consisting of the digits of every integer in nums, separated and kept in the same order they appear in nums. For example, separating 10921 produces [1,0,9,2,1].

Constraints / 限制： - 1 <= nums.length <= 1000 - 1 <= nums[i] <= 10^5 （所以每個數字最多有 6 位 / each number has at most 6 digits）

Example / 範例：

Input:  nums = [13, 25, 83, 77]
Output: [1, 3, 2, 5, 8, 3, 7, 7]

• 13 → [1,3]，25 → [2,5]，83 → [8,3]，77 → [7,7]，串起來即答案。

名詞解釋 / Glossary

• 整數除法與取餘 / integer division and modulo：x / 10 會把 x 的最後一位「砍掉」（C/C++ 中對正整數是向下取整），x % 10 則取得「最後一位數字」。配合使用就能一位一位地把整數拆開。 / x / 10 drops the last digit of x; x % 10 yields that last digit. Iterating both peels digits off the number one by one.
• 陣列索引 / array indexing：a[i] 表示陣列中第 i 個元素（從 0 開始計數）。 / a[i] is the i-th element of the array, counting from 0.
• 動態記憶體配置 / dynamic memory allocation：在 C 裡用 malloc(n * sizeof(T)) 在堆積（heap）上配置 n 個 T 型別的空間，回傳一個指標。 / In C, malloc(...) allocates memory on the heap and returns a pointer to it; the caller (LeetCode harness) frees it later.
• 指標 / pointer：儲存「某個記憶體位址」的變數。int* 表示指向 int 的指標。透過 *p 解參考可以讀寫該位址的值。 / A variable that holds a memory address. int* points at an int; you read/write through it.
• returnSize 輸出參數 / returnSize out-parameter：LeetCode 的 C 介面用一個指標 int* returnSize 讓你「告訴呼叫端答案陣列有多長」。你必須在函式結束前寫入 *returnSize = 長度;，否則回傳的陣列長度會是未定義行為。 / LeetCode's C harness passes a pointer so your function can report the output length. You must set *returnSize before returning, or the harness can't read your answer correctly.
• std::vector<int> (C++)：C++ 標準函式庫提供的可變長度陣列，會自動管理記憶體。 / A dynamically-sized array container from the C++ STL that manages its own memory.
• std::to_string (C++)：把數字轉成字串，例如 to_string(13) 回傳 "13"。把字元 '1' 變回整數時用 '1' - '0' = 1。 / Converts a number to its decimal string. To turn a digit char back into an int, subtract '0'.
• 範圍式 for 迴圈 / range-based for：for (int x : nums) 依序拿出 nums 裡的每個元素，無需手動寫索引。 / Iterates through every element of nums without writing an index variable.

思路

這題本質是「模擬」：題目沒有要求任何巧妙的最佳化，重點是把每個整數的位數依從高位到低位的順序放進答案。直覺的暴力作法就是最佳作法：對每個整數，把它的每一位數抓出來，依正確順序追加到結果陣列。問題只在於——「從低位到高位」用 % 10、/ 10 一次取一位很容易，但這樣得到的順序是反的（例如 13 會先得到 3 再得到 1），所以我們先把抓到的數字暫存進一個小緩衝區 buf，再「倒著」寫進答案陣列，這樣就還原成原本的順序。另一條等價的路徑是把整數先轉成字串，由左到右逐字元減去 '0'；在 C 裡較麻煩，但在 C++ 裡用 to_string 非常乾淨。由於 nums[i] <= 10^5，每個數字最多 6 位，最多 1000 個數字 → 答案最多 6000 個元素，所以記憶體和時間都非常寬鬆。

The task is pure simulation: there's no clever optimisation to discover — for each integer, append its digits in left-to-right order to the output. The natural way to peel digits off an integer is x % 10 followed by x /= 10, which yields the least-significant digit first (so 13 produces 3 then 1). To recover the original order, we stash those digits in a small fixed-size buffer and then copy the buffer back into the answer in reverse. An equivalent approach is to convert the integer to a decimal string and walk it left-to-right, subtracting '0' from each character — clean in C++ via std::to_string, slightly more boilerplate in C. The constraints (nums[i] ≤ 10^5, at most 1000 numbers) cap the answer at 6000 entries, so even a naive implementation is plenty fast; the only real trap is the digit-order reversal.

逐步走查 / Walkthrough

用第一個範例 nums = [13, 25, 83, 77] 一步步追蹤 C 解法。idx 是答案陣列下一個要寫入的位置；buf 是暫存反序數字的小陣列；cnt 是 buf 中已存的位數。

結果與題目期望輸出完全相符 ✓。 / Output matches the expected [1,3,2,5,8,3,7,7].

Solution — C

/*
 * 演算法 / Algorithm:
 *   逐個整數處理；用 x%10 / x/=10 反序取出每一位數，暫存到 buf，
 *   再把 buf 反向複製到答案陣列，順序就恢復成「高位 → 低位」。
 *   For each integer, peel digits via x%10 / x/=10 (which yields them in
 *   reverse), stash into a small buffer, then copy back reversed so the
 *   final order is most-significant first.
 */

#include <stdlib.h>   // for malloc / 提供 malloc

int* separateDigits(int* nums, int numsSize, int* returnSize) {
    // 每個數字 ≤ 10^5，最多 6 位；總長 ≤ 6 * numsSize 已綽綽有餘
    // Each number ≤ 10^5 has at most 6 digits, so 6*numsSize is a safe upper bound.
    int cap = 6 * numsSize;

    // malloc 在 heap 配置一塊空間，回傳指向第一個 int 的指標
    // malloc allocates the buffer on the heap; we return this pointer to LeetCode.
    int* ans = (int*)malloc(sizeof(int) * cap);

    int idx = 0;  // ans 中下一個要寫入的位置 / next write slot in ans

    // 依序處理 nums 中的每一個整數 / iterate over each input number
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];   // 取出當前整數的「複本」以便破壞性地除以 10 / mutable copy

        int buf[8];        // 暫存反序數字；最多 6 位，給 8 是保險 / scratch buffer
        int cnt = 0;       // buf 內目前已存的位數 / how many digits collected

        // 用 mod / div 從低位往高位剝出每一位
        // Peel digits from least-significant to most-significant.
        // 題目保證 nums[i] >= 1，所以 x 一開始一定 > 0，至少跑一次
        // The constraint nums[i] >= 1 guarantees the loop runs at least once,
        // so we don't need a special case for x == 0.
        while (x > 0) {
            buf[cnt++] = x % 10;  // 取得最後一位 / extract trailing digit
            x /= 10;              // 砍掉最後一位 / drop trailing digit
        }

        // 反向把 buf 倒回 ans：buf 是反序的，從尾巴往前讀就是正序
        // Copy buf into ans in reverse so the digits regain MSB-first order.
        for (int j = cnt - 1; j >= 0; j--) {
            ans[idx++] = buf[j];  // 寫入並推進 idx / write & advance
        }
    }

    // 透過 returnSize 指標把答案長度回報給 LeetCode
    // Tell the harness how long the answer array is via the out-parameter.
    *returnSize = idx;
    return ans;  // LeetCode 之後會負責 free / harness frees this later
}

Solution — C++

/*
 * 演算法 / Algorithm:
 *   對每個整數呼叫 to_string 取得它的十進位字串，再把每個字元減去 '0'
 *   就得到對應的 int 位數，依序 push_back 進結果 vector。
 *   For each integer, convert to a decimal string and push each
 *   (char - '0') into the answer vector — already in MSB-first order.
 */

#include <vector>      // std::vector：動態長度陣列 / dynamic array
#include <string>      // std::to_string：int → string
using namespace std;

class Solution {
public:
    vector<int> separateDigits(vector<int>& nums) {
        vector<int> ans;          // 答案容器，會自動擴容 / output, grows automatically
        ans.reserve(nums.size() * 6);  // 預留容量，減少重新配置 / pre-allocate to avoid reallocs

        // 範圍式 for 迴圈：依序取出 nums 中每個元素
        // Range-based for: visit each element of nums in order.
        for (int x : nums) {
            // to_string 把整數轉成十進位字串，例如 13 → "13"
            // to_string converts the int to its decimal text form.
            string s = to_string(x);

            // 對字串的每個字元 c，'c' - '0' 把它變回 0~9 的整數
            // For each char c, (c - '0') maps '0'..'9' to 0..9 (ASCII arithmetic).
            for (char c : s) {
                ans.push_back(c - '0');  // 追加到答案末端 / append digit
            }
        }
        return ans;   // vector 會以值回傳，內含全部位數 / returned by value
    }
};

複雜度 / Complexity

• Time: O(N · D)，其中 N = nums.length、D 是單一數字的位數（這裡 ≤ 6）。每個數字只被剝開一次，每位數做常數工作。 / Each integer is decomposed once, each digit handled in O(1); D is bounded by ~6 because nums[i] ≤ 10^5, so this is effectively linear in input size.
• Space: O(N · D) — 主要花在輸出陣列本身（題目要求回傳這個陣列，不算「額外」空間，但仍要配置）。其他工作空間（C 的 buf、C++ 的 s）都是 O(D) 常數大小。 / Dominated by the output array; auxiliary scratch space is O(D), i.e. constant.

Pitfalls & Edge Cases

• 位數順序顛倒 / Digit-order reversal：% 10、/ 10 取得的是「低位到高位」的反序。新手最常見錯誤就是直接把 3, 1 推進答案而忘了反轉。本解法用 buf 暫存後反向複製來避開。 / The most common bug: forgetting that x % 10 gives the last digit first. Always reverse before appending.
• returnSize 沒有設定 / Forgetting *returnSize：在 C 介面，若沒寫入 *returnSize，LeetCode 無法知道答案多長，會回傳亂數長度。本解法在 return 前明確設定。 / In the C version, you must assign *returnSize before returning — otherwise the harness reads garbage.
• 配置太小的陣列 / Under-allocating ans in C：若用 malloc(sizeof(int) * numsSize)（只配 N 個位置）就會越界寫入。要乘上「每個數字的最大位數」上限。本解法用 6 * numsSize。 / Allocating only numsSize slots overflows the buffer. Multiply by the per-element digit cap (6).
• 誤用 int 字元 / Mixing char and int in C++：'1' - '0' 是 int 1，不是字元；如果直接 ans.push_back(c)，存進去的是 ASCII 49 而不是 1。 / '1' - '0' evaluates to the integer 1; pushing the raw char would store ASCII codes (49 for '1') instead of digit values.
• 題目保證 nums[i] >= 1 / Guarantee nums[i] >= 1：因此 while (x > 0) 一定會至少跑一次，不需要為 x == 0 寫特例。如果題目允許 0，需要額外加 if (x == 0) buf[cnt++] = 0;。 / Because inputs are strictly positive, the peeling loop always runs at least once; if zeros were allowed, you'd need a special case so a literal 0 still gets recorded.
• 記憶體釋放 / Memory ownership in C：呼叫端（LeetCode 評測程式）會負責 free(ans)，所以函式內不可以提早釋放。 / Don't free ans inside your function — the harness owns and frees it.