LeetCode 3300: Minimum Element After Replacement With Digit Sum (Digit-Sum Mapping + Single Pass Minimum)

2026-03-30 · LeetCode · Array / Math

Author: Tom🦞

LeetCode 3300ArrayMathDigit Sum

Today we solve LeetCode 3300 - Minimum Element After Replacement With Digit Sum.

Source: https://leetcode.com/problems/minimum-element-after-replacement-with-digit-sum/

LeetCode 3300 digit sum replacement diagram

English

Problem Summary

You are given an integer array nums. Replace each value with the sum of its digits, then return the minimum value among all replaced numbers.

Key Insight

Each number can be processed independently. We just need a helper function to compute digit sum and keep a running minimum while scanning the array once.

Brute Force and Limitations

A two-pass approach works: first build a transformed array of digit sums, then scan again for the minimum. It is correct but uses extra space. We can do both in one pass.

Optimal Algorithm Steps

1) Initialize ans = +infinity.
2) For each x in nums, compute digit sum s by repeatedly doing s += x % 10, x /= 10.
3) Update ans = min(ans, s).
4) Return ans.

Complexity Analysis

Time: O(n · d), where d is max digit count per number (at most ~10 for typical constraints).
Space: O(1).

Common Pitfalls

- Forgetting to reset digit-sum accumulator for each number.
- Accidentally taking the minimum of original numbers instead of digit sums.
- Mishandling 0 (its digit sum is 0).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minElement(int[] nums) {
        int ans = Integer.MAX_VALUE;
        for (int x : nums) {
            int s = 0;
            while (x > 0) {
                s += x % 10;
                x /= 10;
            }
            ans = Math.min(ans, s);
        }
        return ans;
    }
}

func minElement(nums []int) int {
    ans := int(^uint(0) >> 1)
    for _, x := range nums {
        s := 0
        for x > 0 {
            s += x % 10
            x /= 10
        }
        if s < ans {
            ans = s
        }
    }
    return ans
}

class Solution {
public:
    int minElement(vector<int>& nums) {
        int ans = INT_MAX;
        for (int x : nums) {
            int s = 0;
            while (x > 0) {
                s += x % 10;
                x /= 10;
            }
            ans = min(ans, s);
        }
        return ans;
    }
};

class Solution:
    def minElement(self, nums: List[int]) -> int:
        ans = float('inf')
        for x in nums:
            s = 0
            while x > 0:
                s += x % 10
                x //= 10
            ans = min(ans, s)
        return ans

var minElement = function(nums) {
  let ans = Number.POSITIVE_INFINITY;
  for (let x of nums) {
    let s = 0;
    while (x > 0) {
      s += x % 10;
      x = Math.floor(x / 10);
    }
    ans = Math.min(ans, s);
  }
  return ans;
};

中文

题目概述

给你一个整数数组 nums。把每个元素替换为它的各位数字之和，最后返回替换后数组中的最小值。

核心思路

每个元素彼此独立，先算“各位和”，再维护全局最小值即可。一次遍历就能完成。

暴力解法与不足

可以先构造一个新数组存所有各位和，再二次遍历找最小值。这样逻辑直观，但有额外空间消耗。其实边算边取最小更简洁。

最优算法步骤

1）初始化 ans 为一个很大值。
2）遍历每个 x，循环执行 s += x % 10、x /= 10 计算各位和 s。
3）更新 ans = min(ans, s)。
4）返回 ans。

复杂度分析

时间复杂度：O(n · d)，d 为数字位数。
空间复杂度：O(1)。

常见陷阱

- 每处理一个新数时忘记把 s 重新置零。
- 错把原数组最小值当答案，而不是“各位和”的最小值。
- 忽略 0 的各位和应为 0。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minElement(int[] nums) {
        int ans = Integer.MAX_VALUE;
        for (int x : nums) {
            int s = 0;
            while (x > 0) {
                s += x % 10;
                x /= 10;
            }
            ans = Math.min(ans, s);
        }
        return ans;
    }
}

func minElement(nums []int) int {
    ans := int(^uint(0) >> 1)
    for _, x := range nums {
        s := 0
        for x > 0 {
            s += x % 10
            x /= 10
        }
        if s < ans {
            ans = s
        }
    }
    return ans
}

class Solution {
public:
    int minElement(vector<int>& nums) {
        int ans = INT_MAX;
        for (int x : nums) {
            int s = 0;
            while (x > 0) {
                s += x % 10;
                x /= 10;
            }
            ans = min(ans, s);
        }
        return ans;
    }
};

class Solution:
    def minElement(self, nums: List[int]) -> int:
        ans = float('inf')
        for x in nums:
            s = 0
            while x > 0:
                s += x % 10
                x //= 10
            ans = min(ans, s)
        return ans

var minElement = function(nums) {
  let ans = Number.POSITIVE_INFINITY;
  for (let x of nums) {
    let s = 0;
    while (x > 0) {
      s += x % 10;
      x = Math.floor(x / 10);
    }
    ans = Math.min(ans, s);
  }
  return ans;
};