How do you calculate the minimum element after replacing numbers with digit sums?

Iterate through the array, compute each number's digit sum, and track the minimum value encountered.

Can this approach handle single-digit numbers or large integers efficiently?

Yes, single-digit numbers remain unchanged, and digit sums for large numbers can be computed efficiently with division or string conversion.

Does the order of elements affect the final minimum?

No, since all elements are transformed independently, the order does not affect the resulting minimum value.

Is it necessary to store the transformed array?

No, you can compute each digit sum and compare it with a running minimum to reduce space usage.

What is the main pattern behind Minimum Element After Replacement With Digit Sum?

The key pattern is array plus math: transform each array element by digit sum calculation, then identify the smallest result.

#3300

Easy

auto_awesome数组·数学

LeetCode 题解工作台

替换为数位和以后的最小元素

给你一个整数数组 nums 。请你将 nums 中每一个元素都替换为它的各个数位之和。请你返回替换所有元素以后 nums 中的最小元素。示例 1：输入： nums = [10,12,13,14] 输出： 1 解释： nums 替换后变为 [1, 3, 4, 5] ，最小元素为 1 。…

数组数学

题目描述

给你一个整数数组 nums 。

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

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

示例 1：

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

输出：1

解释：

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

示例 2：

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

输出：1

解释：

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

示例 3：

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

输出：10

解释：

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

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 10⁴

lightbulb

解题思路

方法一：模拟

我们可以遍历数组 $\textit{nums}$ ，对于每个数 $x$ ，我们计算其各个数位之和 $y$ ，取所有 $y$ 中的最小值即为答案。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 和 $M$ 分别是数组 $\textit{nums}$ 的长度和数组中的最大值。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def minElement(self, nums: List[int]) -> int:
        return min(sum(int(b) for b in str(x)) for x in nums)

speed

复杂度分析

指标	值
时间	complexity is O(n * k), where n is the array length and k is the number of digits in the largest number. Space complexity can be O(1) if using a running minimum without storing the transformed array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They may ask how to efficiently compute the digit sum without converting to string.
question_mark
Expect questions on handling edge cases like single-digit numbers or maximum constraints.
question_mark
They might test optimization for in-place minimum calculation versus storing intermediate results.

warning

常见陷阱

外企场景

error
Forgetting to replace all numbers before computing the minimum can yield incorrect results.
error
Incorrectly summing digits by assuming fixed-length numbers instead of iterating through all digits.
error
Using extra arrays unnecessarily when a running minimum suffices, increasing space complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of the minimum, return the maximum element after digit sum replacement.
arrow_right_alt
Apply the digit sum replacement repeatedly until all numbers are single-digit, then return the minimum.
arrow_right_alt
Replace only numbers above a certain threshold with their digit sum and return the smallest value.

help

常见问题

外企场景

继续练习

#3296 移山所需的最少秒数 #3289 数字小镇中的捣蛋鬼 #3312 查询排序后的最大公约数