3300. Minimum Element After Replacement With Digit Sum

題目 / Problem

中文： 給你一個整數陣列 nums。把陣列中的每個元素，替換成「它各個位數的數字和」。回傳替換完成後陣列中的最小元素。

English: You are given an integer array nums. Replace every element with the sum of its digits. Return the minimum element in the array after all replacements.

約束 / Constraints: - 1 <= nums.length <= 100 - 1 <= nums[i] <= 10^4（所以每個數字最多 5 位數 / so each number has at most 5 digits）

範例 / Example: - Input: nums = [10, 12, 13, 14] - 替換過程：10 → 1+0 = 1、12 → 1+2 = 3、13 → 1+3 = 4、14 → 1+4 = 5 - 替換後變成 [1, 3, 4, 5]，最小值是 1。 - Output: 1

名詞解釋 / Glossary

• 數字和 / Digit sum：把一個整數的每一位數字相加。例如 199 → 1+9+9 = 19。It is the result of adding up each individual digit of a number.
• 取餘數 % / Modulo operator：n % 10 會得到 n 的「個位數」。例如 123 % 10 = 3。n % 10 gives the last (rightmost) digit of n.
• 整數除法 / / Integer division：在 C/C++ 中兩個整數相除會自動去掉小數，n / 10 等於「砍掉個位數」。例如 123 / 10 = 12。Dividing two integers drops the fraction, so n / 10 removes the last digit.
• 遍歷 / Iterate (traverse)：用迴圈把陣列從頭到尾走一遍，逐一處理每個元素。To visit every element of the array one by one with a loop.
• INT_MAX：C/C++ 標準庫定義的「int 能表示的最大值」，常用來當作「目前還沒找到的最小值」的初始值。The largest possible int value; a handy initial value when searching for a minimum.

思路

這題其實非常直接，沒有複雜的演算法。我們要做兩件事：第一，對每個數字算出它的「數字和」；第二，在所有數字和裡找出最小的那一個。怎麼算數字和？最直覺的方法是把數字當成字串、一個字元一個字元加起來，但在 C 裡更乾淨的做法是用數學：不斷地用 n % 10 取出個位數加進總和，再用 n / 10 砍掉個位數，直到數字變成 0 為止。這樣就把每一位都掃過了。算最小值也很簡單：準備一個變數 ans 初始設成一個很大的值（INT_MAX），遍歷時只要遇到更小的數字和就更新它。因為陣列最多 100 個元素、每個數字最多 5 位，整體工作量極小，這個一遍掃描的做法已經是最優解，不需要排序或任何額外資料結構。

This problem is deliberately simple — no fancy algorithm is needed. There are two jobs: compute the digit sum of each number, then track the smallest digit sum seen so far. To get a digit sum, the cleanest approach in C is arithmetic rather than string conversion: repeatedly take the last digit with n % 10, add it to a running total, then chop that digit off with n / 10, looping until n becomes 0. To find the minimum, start an answer variable at a very large value (INT_MAX) and lower it whenever a smaller digit sum appears. Since there are at most 100 numbers and each has at most 5 digits, the workload is tiny, and this single pass is already optimal — no sorting or extra data structures required.

逐步走查 / Walkthrough

以 nums = [10, 12, 13, 14] 為例，ans 初始 = INT_MAX（很大）。 Using nums = [10, 12, 13, 14], ans starts at INT_MAX (very large).

遍歷結束，回傳 ans = 1。 / Loop ends, return ans = 1. ✅

Solution — C

// 演算法 / Algorithm:
// 對每個數字用「% 10 取個位、/ 10 去個位」反覆算出數字和，
// 同時用 ans 追蹤所有數字和的最小值，一次遍歷即可。
// For each number, get its digit sum via repeated %10 and /10,
// while keeping ans as the running minimum over a single pass.

#include <limits.h>   // 為了使用 INT_MAX / for INT_MAX

int minElement(int* nums, int numsSize) {
    int ans = INT_MAX;                 // ans 設為最大值，之後只會變小 / start huge so any real sum is smaller

    for (int i = 0; i < numsSize; i++) {   // 遍歷陣列每個元素 / visit every element by index
        int n = nums[i];               // 取出目前的數字，n 是工作副本 / working copy we can shrink
        int sum = 0;                   // 累加這個數字的各位 / accumulator for this number's digit sum

        while (n > 0) {                // 還有位數沒處理就繼續 / keep going while digits remain
            sum += n % 10;             // n % 10 是個位數，加進 sum / add the last digit
            n /= 10;                   // 整數除法砍掉個位 / drop the last digit (integer division)
        }

        if (sum < ans) {               // 找到更小的數字和就更新 / found a smaller sum -> record it
            ans = sum;                 // 更新最小值 / update the minimum
        }
    }

    return ans;                        // 回傳最小數字和 / return the smallest digit sum
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同：對每個元素計算數字和（反覆 %10 與 /10），
// 用 range-for 遍歷並用 min 維護最小值。
// Same as the C version: digit sum per element, tracked with a running min.

#include <vector>      // std::vector 動態陣列 / dynamic array container
#include <algorithm>   // std::min
#include <climits>     // INT_MAX
using namespace std;

class Solution {
public:
    int minElement(vector<int>& nums) {
        int ans = INT_MAX;             // 初始設為最大值 / start at the largest int

        for (int x : nums) {           // range-for：x 依序取得每個元素的值 / iterate values directly
            int n = x;                 // 可修改的副本，避免改動原始資料 / mutable copy
            int sum = 0;               // 這個數字的數字和 / digit sum for this number

            while (n > 0) {            // 逐位處理直到 n 變 0 / process each digit until none left
                sum += n % 10;         // 取個位並累加 / add last digit
                n /= 10;               // 去掉個位 / remove last digit
            }

            ans = min(ans, sum);       // std::min 取兩者較小者 / keep the smaller of the two
        }

        return ans;                    // 回傳結果 / return the answer
    }
};

複雜度 / Complexity

• Time: O(n · d) — n 是陣列長度，d 是每個數字的位數（這裡最多 5）。我們對每個元素各掃一遍它的位數。由於 d 是很小的常數，實務上可視為 O(n)。 / We touch each of the n numbers and loop over its d digits; d ≤ 5 here, so it is effectively linear.
• Space: O(1) — 只用了 ans、n、sum 幾個變數，沒有額外配置和輸入大小成正比的空間。 / Only a few scalar variables; no extra memory that grows with input.

Pitfalls & Edge Cases

• ans 初始值要夠大 / Initialize ans large enough. 若初始設成 0 或某個小數，最小值永遠不會被更新而出錯；用 INT_MAX 保證第一個數字和一定會被記錄。/ Starting at 0 would never get replaced; INT_MAX guarantees the first sum wins.
• while (n > 0) 而非 n >= 0 / Loop condition must be n > 0. 若寫成 >=，當 n 變成 0 時 n /= 10 永遠還是 0，會造成無窮迴圈。/ Using >= would loop forever once n hits 0.
• 約束保證 nums[i] >= 1 / Inputs are always positive. 所以不必處理 0 或負數；若數字可能為負，需先取絕對值，否則 % 10 在 C/C++ 對負數的行為會出錯。/ No need to handle 0 or negatives here; negatives would break % 10 and need abs() first.
• 不需要真的「替換」原陣列 / No need to actually mutate the array. 題目說「替換」，但我們只要最小數字和，邊算邊比即可，省下寫回的步驟。/ We only need the minimum, so computing on the fly is enough.