3300. Minimum Element After Replacement With Digit Sum

Problem Description

You are given an integer array nums. You need to replace each element in nums with the sum of its digits. After performing this transformation on all elements, return the minimum element from the transformed array.

Intuition

The task requires us to transform each number in the array nums by calculating the sum of its digits. This involves converting each integer to a string, iterating over each character in the string (representing a digit), and summing these digits after converting them back to integers. Once all numbers have been transformed, the goal is to find and return the smallest value from these transformed numbers.

The approach is straightforward: iterate over each number in the input array, compute the sum of its digits, and keep track of the minimum such sum encountered. This ensures that you correctly determine the minimum element from the digit sums effectively.

Learn more about Math patterns.

Solution Approach

The problem can be solved using a simple simulation approach. Here's how it is done:

Initialize a Minimum Tracker: Start with a variable to keep track of the minimum digit sum encountered as you iterate over the array. This can be initialized to a large number or the result of the first transformation.
Transform Each Number: For each number x in the array nums, perform the following operations:
- Convert the number to a string to iterate over its digits.
- Calculate the sum of the digits by converting each character back to an integer and accumulating their sum.
Update Minimum: Compare the current digit sum to the minimum value tracked so far. If it is smaller, update the minimum.
Return the Result: After processing all numbers, return the minimum digit sum found.

The implementation of this approach is straightforward:

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

The core logic is wrapped within a single line using Python's min() function and list comprehensions, effectively computing and comparing each number's digit sum to find and return the smallest one.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take an example array: nums = [38, 55, 62]. We want to replace each number with the sum of its digits and find the minimum of these sums.

Initialize a Minimum Tracker: Start by assuming an extremely large minimum value, but if we're implementing efficiently, directly use the result of the first transformation.
Transform Each Number:
- For the first number, 38:
  - Convert 38 to a string, iterate over each character: '3' and '8'.
  - Convert these characters to integers and sum them: 3 + 8 = 11.
- For the second number, 55:
  - Convert 55 to a string, iterate over each character: '5' and '5'.
  - Convert these characters to integers and sum them: 5 + 5 = 10.
- For the third number, 62:
  - Convert 62 to a string, iterate over each character: '6' and '2'.
  - Convert these characters to integers and sum them: 6 + 2 = 8.
Update Minimum:
- After processing 38, the minimum digit sum is 11.
- After processing 55, update the minimum to 10 since 10 < 11.
- After processing 62, update the minimum to 8 since 8 < 10.
Return the Result: After iterating through all numbers, the minimum digit sum found is 8.

This example concludes that the smallest value from the transformed array is 8, corresponding to the number 62 in the original array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minElement(self, nums: List[int]) -> int:
5        # Calculate the minimum sum of the digits of the elements in the list
6        return min(sum(int(digit) for digit in str(number)) for number in nums)
7

1class Solution {
2    public int minElement(int[] nums) {
3        int ans = 100; // Initialize the answer with a large value.
4        for (int number : nums) { // Iterate over each number in the array.
5            int digitSum = 0; // This will hold the sum of digits for the current number.
6            int currentNumber = number; // Store the current number to avoid altering the loop variable.
7          
8            // Calculate the sum of digits.
9            while (currentNumber > 0) {
10                digitSum += currentNumber % 10; // Add the last digit to digitSum.
11                currentNumber /= 10; // Remove the last digit from currentNumber.
12            }
13          
14            // Update the minimum digit sum found so far.
15            ans = Math.min(ans, digitSum);
16        }
17      
18        return ans; // Return the smallest digit sum.
19    }
20}
21

1#include <vector>
2#include <algorithm> // for std::min
3using namespace std;
4
5class Solution {
6public:
7    int minElement(vector<int>& nums) {
8        int ans = 100; // Initialize 'ans' with a large value assuming sum of digits will be less than 100.
9      
10        // Iterate through each number in the vector 'nums'.
11        for (int x : nums) {
12            int sumOfDigits = 0; // Initialize the sum of digits for the current number.
13      
14            // Calculate the sum of the digits of the number 'x'.
15            while (x > 0) {
16                sumOfDigits += x % 10; // Add the last digit of 'x' to 'sumOfDigits'.
17                x /= 10; // Remove the last digit from 'x'.
18            }
19      
20            // Update 'ans' with the minimum sum of digits found so far.
21            ans = min(ans, sumOfDigits);
22        }
23      
24        return ans; // Return the smallest sum of digits found.
25    }
26};
27

1// Function to find the minimum sum of digits among numbers in the array
2function minElement(nums: number[]): number {
3    // Initialize the minimum answer with a large value
4    let ans: number = 100;
5
6    // Loop through each number in the array
7    for (let num of nums) {
8        let digitSum = 0; // Initialize a variable to store the sum of digits
9      
10        // Calculate the sum of digits of the current number
11        while (num) {
12            digitSum += num % 10; // Add the last digit to the sum
13            num = Math.floor(num / 10); // Remove the last digit
14        }
15      
16        // Update the minimum sum of digits found so far
17        ans = Math.min(ans, digitSum);
18    }
19
20    // Return the minimum sum of digits
21    return ans;
22}
23

Time and Space Complexity

The given code calculates the minimum sum of the digits for each number in the list nums. The time complexity is determined by two main operations: iterating over each element in nums and calculating the sum of digits.

Converting a number to a string (str(x)) takes O(\log M) time, where M is the maximum value within nums, due to the number of digits.
Parsing each character of the string into an integer and summing them also takes O(\log M) time, as there are \log M digits in the number.

Thus, for each of the n numbers in the list, these operations lead to a time complexity of O(n \times \log M).

The space complexity is O(1) since the algorithm uses a constant amount of space regardless of the input size, as it only requires space for variables that store temporary data such as the sum of digits and the minimum value.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: