3300. Minimum Element After Replacement With Digit Sum

Array
Math

TIME

O(n * D)

SPACE

O(1)

Intuition

Each number is independent. Replace a number by repeatedly taking its last digit and adding it to a running sum, then removing that digit.

After computing the digit sum for every number, keep the smallest value seen.

Approach

Initialize the answer to infinity.
For each number in nums:
- compute its digit sum using modulo 10 and integer division by 10
- update the answer with the smaller digit sum
Return the answer.

Complexity

Let D be the maximum number of digits in any number.

Time: O(n * D)
Space: O(1)

Since nums[i] <= 10^4, D is at most 5.

Edge Cases

Single element array -> return that element's digit sum
One-digit numbers -> digit sum is the number itself
Values like 10000 -> zeros do not change the sum

Code

from typing import List


class Solution:
    def minElement(self, nums: List[int]) -> int:
        """
        3300. Minimum Element After Replacement With Digit Sum
        Time: O(n * D)
        Space: O(1)
        """
        def digit_sum(num: int) -> int:
            total = 0
            while num > 0:
                total += num % 10
                num //= 10
            return total

        return min(digit_sum(num) for num in nums)

/**
 * 3300. Minimum Element After Replacement With Digit Sum
 * Time: O(n * D)
 * Space: O(1)
 */
class Solution {
    public int minElement(int[] nums) {
        int answer = Integer.MAX_VALUE;

        for (int num : nums) {
            answer = Math.min(answer, digitSum(num));
        }

        return answer;
    }

    private int digitSum(int num) {
        int total = 0;
        while (num > 0) {
            total += num % 10;
            num /= 10;
        }
        return total;
    }
}