Problem Statement in English

You’re given a 0-indexed integer array nums consisting of positive integers. You must return the minimum element in nums after replacing every element with the sum of its digits.

Approach

Credit: I got this solution from a post in the LeetCode discussion.

You could just brute force the solution, but there’s something better we can do.

Since the question guarantees that the input is a 4 digit number at most, we can exploit place values to calculate the digit sum in O(1) time for each number.

Consider a number n. Let it be represented as abcd where a, b, c, and d are the digits of the number. The digit sum of n is a + b + c + d and n = 1000a + 100b + 10c + d.

We can then rewrite n as 999a + 99b + 9c + (a + b + c + d). Notice that the last term is the digit sum that we established earlier.

Thus digitSum(n) = n - 999a - 99b - 9c, and:

digitSum(n) = n - 9 * (111a + 11b + c)

Now, going back to n, if we perform integer division by 10, we get abcd // 10 = abc. abc is equal to 100a + 10b + c.

If we perform integer division by 100, we get abcd // 100 = ab. ab is equal to 10a + b.

Finally, if we perform integer division by 1000, we get abcd // 1000 = a.

Now going back to digitSum(n) = n - 9 * (111a + 11b + c), we can rewrite it as:

digitSum(n) = n - 9 * ((100a + 10b + c) + (10a + b) + a) and this is equal to:

digitSum(n) = n - 9 * ((n//10) + (n//100) + (n//1000))

And this is our final formula to calculate the digit sum in $O(1)$ time for each number.

We can then iterate through the array and calculate the minimum element after replacing with digit sum using this formula.

And we’re done!

Solution in Python


class Solution:
    def minElement(self, nums: List[int]) -> int:
        res = 36
        for n in nums:
            res = min(res, n - 9 * ((n//10) + (n//100) + (n//1000) + (n//10000)))
            
        return res

Complexity

  • Time: $O(n)$
    Since we need to iterate through the array once to calculate the minimum element after replacing with digit sum.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space to store the result.

And we are done.