Minimum Element After Replacement With Digit Sum

Difficulty: Easy | Acceptance: 84.80% | Paid: No Topics: Array, Math

You are given an integer array nums.

In one operation, you can replace any element nums[i] with the sum of its digits.

Return the minimum element of nums after performing the operation on each element.

• Examples
• Constraints
• Iterative Digit Sum
• String Conversion
• Functional/Stream Approach

Examples

Input: nums = [10,12,13,14]
Output: 1
Explanation:
- 10 becomes 1 + 0 = 1
- 12 becomes 1 + 2 = 3
- 13 becomes 1 + 3 = 4
- 14 becomes 1 + 4 = 5
The minimum element is 1.

Input: nums = [1,2,3,4]
Output: 1
Explanation:
- 1 becomes 1
- 2 becomes 2
- 3 becomes 3
- 4 becomes 4
The minimum element is 1.

Input: nums = [999,19,199]
Output: 10
Explanation:
- 999 becomes 9 + 9 + 9 = 27
- 19 becomes 1 + 9 = 10
- 199 becomes 1 + 9 + 9 = 19
The minimum element is 10.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 10^9

Iterative Digit Sum

Intuition For each number, extract digits using modulo and division operations, sum them up, and track the minimum across all elements.

Steps

• Initialize minimum value to infinity
• For each number in the array:
  • Calculate sum of digits by repeatedly taking modulo 10 and dividing by 10
  • Update minimum if current sum is smaller
• Return the minimum value found

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

Complexity

• Time: O(n × d) where n is array length and d is maximum digits (at most 10 for 10⁹)
• Space: O(1)
• Notes: Most efficient approach with constant space overhead

String Conversion

Intuition Convert each number to a string, iterate through characters to extract digits, sum them, and find the minimum.

Steps

• Initialize minimum value to infinity
• For each number in the array:
  • Convert number to string
  • Iterate through each character and convert back to digit
  • Sum all digits and update minimum
• Return the minimum value found

class Solution:
    def minElement(self, nums: List[int]) -> int:
        min_val = float('inf')
        for num in nums:
            digit_sum = sum(int(d) for d in str(num))
            min_val = min(min_val, digit_sum)
        return min_val

Complexity

• Time: O(n × d) where n is array length and d is maximum digits
• Space: O(d) for string conversion
• Notes: Slightly less efficient due to string allocation overhead

Functional/Stream Approach

Intuition Use functional programming constructs like map, reduce, and streams to transform the array and find the minimum in a declarative style.

Steps

• Define a digit sum helper function
• Map each element to its digit sum
• Find the minimum of the transformed values
• Return the result

class Solution:
    def minElement(self, nums: List[int]) -> int:
        def digit_sum(n):
            return sum(int(d) for d in str(n))
        
        return min(digit_sum(num) for num in nums)

Complexity

• Time: O(n × d) where n is array length and d is maximum digits
• Space: O(n) for mapped array in JavaScript/TypeScript, O(1) for Java streams
• Notes: More readable but may have higher memory usage due to intermediate arrays