Scale Engineer

Minimum Element After Replacement With Digit Sum

Easy
#2930Time: 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.
Patterns
Math
Data structures
Array

Prompt

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 <= 100
  • 1 <= 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 digitSums of the same size as nums.
  • Iterate through the nums array with an index i from 0 to n-1, where n is the length of nums.
  • For each element nums[i], calculate its digit sum.
  • Store the calculated digit sum in digitSums[i].
  • Initialize a variable minimum to the first element of digitSums.
  • Iterate through the digitSums array from the second element.
  • In each iteration, update minimum if 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 nums is 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.

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem