Minimum Element After Replacement With Digit Sum - Solution & Explanation

Problem Overview: You receive an integer array nums. Replace each number with the sum of its digits (for example, 123 → 1+2+3 = 6). After performing this transformation for every element, return the minimum value in the updated array.

The key observation is that the transformation is independent for each number. You only need a digit-sum operation and a way to track the smallest result.

Approach 1: Iterative Approach (O(n · d) time, O(1) space)

Traverse the array and compute the digit sum for each element. The digit sum can be calculated using repeated modulus and division: digit += num % 10 and num /= 10 until the number becomes zero. Replace the current element with this computed value or simply track it in a temporary variable.

After transforming each element, maintain a running minimum. This approach explicitly follows the problem statement: convert every value first, then determine the minimum. Time complexity is O(n · d), where n is the array length and d is the number of digits per number (at most ~10 for typical constraints). Space complexity remains O(1) since only a few variables are used.

This approach works well when you want clarity and step-by-step transformation of the array. It directly demonstrates the digit-sum calculation using simple arithmetic operations.

Approach 2: Optimize using Single Pass (O(n · d) time, O(1) space)

The optimization removes the need to conceptually store the transformed array. Instead, iterate through nums once, compute the digit sum for the current number, and immediately update the minimum value.

For each element: compute the digit sum using modulus and division, compare it with the current minimum, and update the minimum if needed. Because the result is consumed immediately, there is no extra array or replacement step.

This keeps the algorithm linear with O(n · d) time and constant O(1) space. The improvement is mostly conceptual and memory-efficient, but it is typically what interviewers expect because it avoids unnecessary work.

Both solutions rely on basic operations over an array and simple math digit manipulation. No additional data structures are required.

Recommended for interviews: The single-pass approach. It demonstrates that you understand the transformation and can combine computation with aggregation efficiently. Mentioning the straightforward iterative version first shows clarity, but implementing the optimized single-pass scan highlights practical problem-solving skills.