Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8


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

Output: 1

Explanation:

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

Example 2

1
2
3
4
5
6
7
8


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

Output: 1

Explanation:

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

Example 3

1
2
3
4
5
6
7
8


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] <= 10^4

Solution

Method 1 – Digit Sum Replacement

Intuition

The key idea is to replace each number with the sum of its digits, then find the minimum among these new values. Calculating the digit sum is straightforward and can be done for each element independently.

Approach

  1. For each number in the array, compute the sum of its digits.
  2. Replace the number with its digit sum.
  3. Find and return the minimum value in the modified array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

func minimumSum(nums []int) int {
    ans := 1 << 30
    for _, x := range nums {
        s := 0
        for x > 0 {
            s += x % 10
            x /= 10
        }
        if s < ans { ans = s }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int minimumSum(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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minimumSum(nums: IntArray): Int {
        var ans = Int.MAX_VALUE
        for (x in nums) {
            var s = 0
            var y = x
            while (y > 0) {
                s += y % 10
                y /= 10
            }
            ans = minOf(ans, s)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

def minimum_sum(nums: list[int]) -> int:
    def digit_sum(x: int) -> int:
        s = 0
        while x:
            s += x % 10
            x //= 10
        return s
    return min(digit_sum(x) for x in nums)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn minimum_sum(nums: Vec<i32>) -> i32 {
        nums.into_iter().map(|mut x| {
            let mut s = 0;
            while x > 0 {
                s += x % 10;
                x /= 10;
            }
            s
        }).min().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    minimumSum(nums: number[]): number {
        let ans = Number.MAX_SAFE_INTEGER;
        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;
    }
}

Complexity

  • ⏰ Time complexity: O(n * d), where n is the length of nums and d is the number of digits in the largest number. Each digit is processed once per number.
  • 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.