Skip to content

3300. Minimum Element After Replacement With Digit Sum

Description

You are given an integer array nums.

You replace each element in nums with the sum of its digits.

Return the minimum element in nums after all replacements.

 

Example 1:

Input: nums = [10,12,13,14]

Output: 1

Explanation:

nums becomes [1, 3, 4, 5] after all replacements, with minimum element 1.

Example 2:

Input: nums = [1,2,3,4]

Output: 1

Explanation:

nums becomes [1, 2, 3, 4] after all replacements, with minimum element 1.

Example 3:

Input: nums = [999,19,199]

Output: 10

Explanation:

nums becomes [27, 10, 19] after all replacements, with minimum element 10.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 104

Solutions

Solution 1: Simulation

Thinking

We replace each element by the sum of its digits and then take the minimum. With \(n \le 100\) and \(M \le 10^4\), splitting digits costs only \(O(\log M)\) per value, which is acceptable.

Digit sums are independent, so there is no need to sort or tabulate. A single scan that keeps the running minimum suffices.

For each \(x\) we accumulate its decimal digits and return the minimum among those sums.

We can traverse the array \(\textit{nums}\). For each number \(x\), we calculate the sum of its digits \(y\). The minimum value among all \(y\) is the answer.

The time complexity is \(O(n \times \log M)\), where \(n\) and \(M\) are the length of the array \(\textit{nums}\) and the maximum value in the array, respectively. The space complexity is \(O(1)\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minElement(int[] nums) {
        int ans = 100;
        for (int x : nums) {
            int y = 0;
            for (; x > 0; x /= 10) {
                y += x % 10;
            }
            ans = Math.min(ans, y);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int minElement(vector<int>& nums) {
        int ans = 100;
        for (int x : nums) {
            int y = 0;
            for (; x > 0; x /= 10) {
                y += x % 10;
            }
            ans = min(ans, y);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minElement(nums []int) int {
    ans := 100
    for _, x := range nums {
        y := 0
        for ; x > 0; x /= 10 {
            y += x % 10
        }
        ans = min(ans, y)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minElement(nums: number[]): number {
    let ans: number = 100;
    for (let x of nums) {
        let y = 0;
        for (; x; x = Math.floor(x / 10)) {
            y += x % 10;
        }
        ans = Math.min(ans, y);
    }
    return ans;
}

Comments