# Minimum Element After Replacement With Digit Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-element-after-replacement-with-digit-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-element-after-replacement-with-digit-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
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
## Brute Force using an Auxiliary Array
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Optimal Single-Pass Approach
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a variable `minSum` to `Integer.MAX_VALUE`.
- Iterate through each `num` in the `nums` array.
- For each `num`, calculate its digit sum and store it in a variable `currentSum`.
  - Initialize `currentSum = 0` and `tempNum = num`.
  - While `tempNum > 0`:
    - Add `tempNum % 10` to `currentSum`.
    - Update `tempNum` to `tempNum / 10`.
- Update `minSum` with the minimum of `minSum` and `currentSum`.
- After iterating through all numbers, return `minSum`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def minElement(
        self, nums: List[int]) -> int: return min(sum(int(b) for b in str(x)) for x in nums)

```