题目描述

给你一个整数数组 nums。

请你将 nums 中每一个元素都替换为它的各个数位之 和。

请你返回替换所有元素以后 nums 中的 最小 元素。

样例

输入：nums = [10,12,13,14]

输出：1

解释：

nums 替换后变为 [1, 3, 4, 5]，最小元素为 1。

输入：nums = [1,2,3,4]

输出：1

解释：

nums 替换后变为 [1, 2, 3, 4]，最小元素为 1。

输入：nums = [999,19,199]

输出：10

解释：

nums 替换后变为 [27, 10, 19]，最小元素为 10。

限制

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 10^4

算法

(模拟) $O(n \log S)$

1. 按照题意模拟。通过对 10 取余以及除以 10 求出数字各个数位之和。

时间复杂度

• 遍历数组一次，每个数字 $S$ 都需要 $O(\log S)$ 的时间求出各个数位之和。
• 故总时间复杂度为 $O(n \log S)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minElement(vector<int>& nums) {
        int ans = INT_MAX;

        for (int x : nums) {
            int t = 0;
            while (x) {
                t += x % 10;
                x /= 10;
            }

            if (ans > t)
                ans = t;
        }

        return ans;
    }
};