We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Element After Replacement With Digit Sum

Number: 3606

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, replace each element with the sum of its digits. Return the minimum element of the modified array.

Key Insights

  • Each number is transformed by replacing it with the sum of its digits.
  • The digit sum of a number is calculated by iterating over its digits.
  • In the end, simply return the minimum value from the array after transformation.
  • Since the maximum number is 10^4, the number of digits per number is limited, resulting in a low constant factor.

Space and Time Complexity

Time Complexity: O(n * d) where d is the number of digits in each number (d is at most ~5 for 10^4)
Space Complexity: O(1) additional space, excluding the space for input

Solution

We iterate over each element in the array and compute the sum of its digits. This is done by either converting the number to a string or using arithmetic operations (mod and division) to sum the digits. After each number is replaced, we find and return the smallest value in the updated array.

We use a simple iterative approach that leverages basic arithmetic operations. The key data structure used is just the input array itself, and the process involves scanning the array twice: once for transformation and once for finding the minimum value.

Code Solutions

# Function to compute the sum of digits of a number
def digit_sum(number):
    total = 0
    while number:
        total += number % 10  # add the last digit
        number //= 10         # remove the last digit
    return total

def min_digit_sum(nums):
    # Replace each element with its digit sum
    for i in range(len(nums)):
        nums[i] = digit_sum(nums[i])
    
    # Return the minimum element after replacement
    return min(nums)

# Example usage
nums = [999, 19, 199]
print(min_digit_sum(nums))  # Output: 10
← Back to All Questions