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 <= 1001 <= nums[i] <= 104Problem 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.
In this approach, we will iterate through each number in the array, calculate the sum of its digits, replace the original number with this sum, and finally find the minimum number in the modified array.
This C program defines a helper function digitSum to calculate the sum of digits of a number. In the findMinimumAfterReplacement function, it iterates over the array, applies the digit sum for each element, and finally finds the minimum value among the transformed elements.
Time Complexity: O(n * m), where n is the number of elements in the array, and m is the average number of digits in each number.
Space Complexity: O(1) as we're modifying input array in-place.
This approach calculates the digit sum for each number and maintains the minimum value seen so far during the iteration. This eliminates the need for a separate pass to find the minimum element after transformation.
This approach initializes the minimum with the digit sum of the first element and iteratively updates it while calculating the digit sum of each subsequent number.
Time Complexity: O(n * m)
Space Complexity: O(1).
We can traverse the array 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 nums and the maximum value in the array, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n * m), where n is the number of elements in the array, and m is the average number of digits in each number. |
| Optimize using Single Pass | Time Complexity: O(n * m) |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Transformation | O(n · d) | O(1) | When implementing the problem exactly as described by replacing every element first |
| Single Pass Minimum Tracking | O(n · d) | O(1) | Preferred approach in interviews; compute digit sum and update minimum in one traversal |
Minimum Element After Replacement With Digit Sum || LeetCode Biweekly Contest 140 • codi • 495 views views
Watch 9 more video solutions →Practice Minimum Element After Replacement With Digit Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor