Minimum Element After Replacement With Digit Sum
EasyPrompt
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] <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves two main steps. First, we iterate through the input array nums, and for each number, we calculate the sum of its digits. We store these sums in a new auxiliary array. In the second step, we iterate through this new array to find its minimum element, which is the final answer.
Algorithm
- Create a new integer array
digitSumsof the same size asnums. - Iterate through the
numsarray with an indexifrom 0 ton-1, wherenis the length ofnums. - For each element
nums[i], calculate its digit sum. - Store the calculated digit sum in
digitSums[i]. - Initialize a variable
minimumto the first element ofdigitSums. - Iterate through the
digitSumsarray from the second element. - In each iteration, update
minimumif the current element is smaller. - Return
minimum.
Walkthrough
The core of this method is to separate the calculation of digit sums from finding the minimum. We first declare a new integer array, say digitSums, with the same length as the input nums array. We then loop through each element of nums. Inside the loop, we compute the digit sum for the current number. The digit sum calculation is done by repeatedly taking the number modulo 10 to get the last digit and adding it to a sum, then dividing the number by 10 to process the next digit, until the number becomes zero. The calculated sum is stored in the corresponding index of the digitSums array. After the first loop completes, the digitSums array contains all the replaced values. A second loop is then used to find the minimum value within the digitSums array. We initialize a minVal variable with the first element and then iterate through the rest, updating minVal whenever a smaller element is found. Finally, this minVal is returned.
import java.util.Arrays; class Solution { // Helper function to calculate the sum of digits private int getDigitSum(int n) { int sum = 0; while (n > 0) { sum += n % 10; n /= 10; } return sum; } public int minimumSum(int[] nums) { int n = nums.length; int[] digitSums = new int[n]; // Step 1: Calculate digit sums and store in a new array for (int i = 0; i < n; i++) { digitSums[i] = getDigitSum(nums[i]); } // Step 2: Find the minimum in the new array if (n == 0) { return 0; // Or handle as per problem spec for empty array } int minVal = digitSums[0]; for (int i = 1; i < n; i++) { if (digitSums[i] < minVal) { minVal = digitSums[i]; } } // Alternatively, using Java Streams: // return Arrays.stream(digitSums).min().getAsInt(); return minVal; }}Complexity
Time
O(N * D), where N is the number of elements in `nums` and D is the maximum number of digits in any element. For `nums[i] <= 10^4`, D is at most 5, so the complexity is effectively linear, O(N). The first loop takes O(N * D) and the second loop takes O(N). Total is O(N * D + N) = O(N * D).
Space
O(N), where N is the length of the input array. This is because we create an auxiliary array `digitSums` of size N to store the intermediate results.
Trade-offs
Pros
The logic is simple and easy to understand as it separates the two main tasks (transformation and finding the minimum).
The original input array
numsis not modified.
Cons
It uses extra space proportional to the input size, which is not optimal. For very large inputs, this could be a concern.
This is the most efficient approach. It combines the process of calculating the digit sum and finding the minimum into a single loop. We iterate through the input array just once, calculating the digit sum for each number and immediately comparing it with the minimum sum found so far. This avoids the need for an extra array and a second pass.
Algorithm
- Initialize a variable
minSumtoInteger.MAX_VALUE. - Iterate through each
numin thenumsarray. - For each
num, calculate its digit sum and store it in a variablecurrentSum.- Initialize
currentSum = 0andtempNum = num. - While
tempNum > 0:- Add
tempNum % 10tocurrentSum. - Update
tempNumtotempNum / 10.
- Add
- Initialize
- Update
minSumwith the minimum ofminSumandcurrentSum. - After iterating through all numbers, return
minSum.
Walkthrough
This method optimizes the process by eliminating the need for intermediate storage. We maintain a single variable, minSum, to keep track of the minimum digit sum encountered. We initialize minSum to a very large value, such as Integer.MAX_VALUE, to ensure that the digit sum of the first element will be smaller and correctly set as the initial minimum. We then iterate through each number num in the input array nums. For each num, we calculate its digit sum. This is done using a small inner loop: while the number is greater than 0, we add num % 10 to a currentSum and then update the number by num /= 10. After calculating the currentSum for the number, we compare it with our running minSum. If currentSum is smaller, we update minSum to currentSum. This process is repeated for all numbers in the array. After the loop completes, minSum will hold the overall minimum digit sum, which is the result we return.
class Solution { public int minimumSum(int[] nums) { int minSum = Integer.MAX_VALUE; for (int num : nums) { int currentSum = 0; int tempNum = num; // Calculate the sum of digits for the current number while (tempNum > 0) { currentSum += tempNum % 10; tempNum /= 10; } // Update the overall minimum sum if (currentSum < minSum) { minSum = currentSum; } // Or using Math.min: // minSum = Math.min(minSum, currentSum); } return minSum; }}Complexity
Time
O(N * D), where N is the number of elements in `nums` and D is the maximum number of digits in any element. Since we iterate through the array once and the digit sum calculation is proportional to the number of digits, this is the most efficient time complexity possible.
Space
O(1). We only use a few variables (`minSum`, `currentSum`, `tempNum`) to store intermediate values, regardless of the input size. This is optimal.
Trade-offs
Pros
Highly efficient in terms of both time and space.
Requires only a single pass over the data.
Does not modify the original input array.
Cons
There are no significant cons to this approach; it is the standard and optimal way to solve this problem.
Solutions
Solution
class Solution {public int minElement(int[] nums) { int ans = 100; for (int x : nums) { int y = 0; for (; x > 0; x /= 10) { y += x % 10; } ans = Math.min(ans, y); } return ans; }}class Solution {public: int minElement(vector<int> &nums) { int ans = 100; for (int x : nums) { int y = 0; for (; x > 0; x /= 10) { y += x % 10; } ans = min(ans, y); } return ans; }};class Solution: def minElement( self, nums: List[int]) -> int: return min(sum(int(b) for b in str(x)) for x in nums)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.