LeetCode 1085 - Sum of Digits in the Minimum Number

LeetCode Problem 1085

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

This problem asks us to examine the smallest number in the input array and determine whether the sum of its digits is odd or even.

We are given an integer array nums. The task consists of three clear steps:

1. Find the minimum integer in the array.
2. Compute the sum of its digits.
3. Return:

• 1 if the digit sum is even
• 0 if the digit sum is odd

For example, if the array is [34,23,1,24,75,33,54,8], the smallest number is 1. The sum of its digits is also 1, which is odd, so we return 0.

The constraints are small:

• nums.length ranges from 1 to 100
• nums[i] ranges from 1 to 100

These constraints tell us several useful things. First, the array is guaranteed to contain at least one element, so we never need to handle an empty input. Second, the numbers are very small, meaning any straightforward solution will easily fit within time limits. Since values are at most 100, digit summation is extremely cheap.

There are a few important edge cases to keep in mind. A single-element array is valid, meaning that element is automatically the minimum. Numbers may contain multiple digits, such as 99 or 100, requiring proper digit extraction rather than assuming one digit. We also need to correctly handle cases where the digit sum is exactly even or odd.

Approaches

Brute Force Approach

A brute-force solution would first sort the array to find the minimum element, then compute the sum of its digits, and finally check whether that sum is odd or even.

Sorting guarantees that the first element becomes the minimum number. After identifying it, we repeatedly extract digits using modulo (% 10) and integer division (// 10) to compute the digit sum. Finally, we check parity using % 2.

This approach is correct because sorting guarantees we find the smallest number. However, sorting is unnecessary work because we only need the minimum element, not the entire ordering of the array.

Optimal Approach

The key observation is that we only care about the minimum value, so sorting the entire array is wasteful. Instead, we can directly compute the minimum using a single pass through the array.

Once the minimum number is found, we repeatedly extract digits:

• Take the last digit using % 10
• Add it to the running sum
• Remove the last digit using integer division by 10

After calculating the digit sum, we check whether it is even or odd:

• Even sum → return 1
• Odd sum → return 0

This avoids sorting entirely and reduces the work to a simple linear scan.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(1) or O(n)	Sorts the array just to find the minimum
Optimal	O(n)	O(1)	Finds minimum in one pass, then sums digits

Algorithm Walkthrough

1. Find the minimum value in the array using min(nums) in Python or a simple loop in Go. This works because the problem only depends on the smallest element.
2. Initialize a variable digit_sum to 0. This variable will store the cumulative sum of the digits.
3. Repeatedly process the minimum number while it is greater than 0:

• Extract the last digit using % 10
• Add it to digit_sum
• Remove the processed digit using integer division by 10

4. After all digits are processed, check whether digit_sum is even using % 2.
5. Return 1 if the sum is even, otherwise return 0.

Why it works

The algorithm works because it directly computes exactly what the problem asks for. The minimum element is uniquely determined from the array, and repeated modulo plus division operations correctly decompose any integer into its digits. Since parity is determined by digit_sum % 2, returning 1 for even and 0 for odd always produces the correct answer.

Python Solution

from typing import List

class Solution:
    def sumOfDigits(self, nums: List[int]) -> int:
        minimum_number = min(nums)
        digit_sum = 0

        while minimum_number > 0:
            digit_sum += minimum_number % 10
            minimum_number //= 10

        return 1 if digit_sum % 2 == 0 else 0

The implementation begins by finding the smallest number in the array using min(nums). Since the input is guaranteed to contain at least one number, this operation is always valid.

Next, we initialize digit_sum to track the total of all digits. The while loop repeatedly extracts the last digit with % 10, adds it to the running total, and removes the digit using integer division (// 10).

Finally, the parity of the digit sum is checked using % 2. If the result is 0, the sum is even and we return 1; otherwise, we return 0.

Go Solution

func sumOfDigits(nums []int) int {
	minimumNumber := nums[0]

	for _, num := range nums {
		if num < minimumNumber {
			minimumNumber = num
		}
	}

	digitSum := 0

	for minimumNumber > 0 {
		digitSum += minimumNumber % 10
		minimumNumber /= 10
	}

	if digitSum%2 == 0 {
		return 1
	}

	return 0
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in min() for slices, we manually scan the array to find the smallest value.

The digit extraction process uses integer arithmetic in the same way, % for the last digit and /= 10 to remove it. Integer overflow is not a concern because values are extremely small, at most 100, and the maximum possible digit sum is tiny.

Because the problem guarantees at least one element, accessing nums[0] is safe.

Worked Examples

Example 1

Input: nums = [34,23,1,24,75,33,54,8]

First, we find the minimum value:

Step	Current Number	Minimum So Far
Start	34	34
Compare	23	23
Compare	1	1
Compare	24	1
Compare	75	1
Compare	33	1
Compare	54	1
Compare	8	1

The minimum number is 1.

Now we compute the digit sum:

Iteration	Number	Extracted Digit	Digit Sum
1	1	1	1
End	0	-	1

The digit sum is 1, which is odd.

Result: 0

Example 2

Input: nums = [99,77,33,66,55]

First, find the minimum:

Step	Current Number	Minimum So Far
Start	99	99
Compare	77	77
Compare	33	33
Compare	66	33
Compare	55	33

The minimum number is 33.

Now compute the digit sum:

Iteration	Number	Extracted Digit	Digit Sum
1	33	3	3
2	3	3	6
End	0	-	6

The digit sum is 6, which is even.

Result: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array once to find the minimum, and digit summation takes constant time
Space	O(1)	Only a few variables are used regardless of input size

The dominant cost is finding the minimum element, which requires traversing all n numbers once. Since each number is at most 100, digit summation takes at most three iterations and is effectively constant time. Therefore, the overall complexity is linear.

Test Cases

solution = Solution()

assert solution.sumOfDigits([34, 23, 1, 24, 75, 33, 54, 8]) == 0  # Example 1, odd digit sum
assert solution.sumOfDigits([99, 77, 33, 66, 55]) == 1  # Example 2, even digit sum

assert solution.sumOfDigits([1]) == 0  # Single element, odd digit sum
assert solution.sumOfDigits([2]) == 1  # Single element, even digit sum

assert solution.sumOfDigits([10]) == 0  # Digit sum = 1, odd
assert solution.sumOfDigits([11]) == 1  # Digit sum = 2, even
assert solution.sumOfDigits([100]) == 0  # Digit sum = 1, odd

assert solution.sumOfDigits([50, 20, 3]) == 0  # Minimum is 3, odd
assert solution.sumOfDigits([88, 42, 24]) == 1  # Minimum is 24, sum = 6

assert solution.sumOfDigits([99, 98, 97]) == 0  # Minimum is 97, sum = 16, even -> return 1
assert solution.sumOfDigits([18, 27, 36]) == 0  # Minimum is 18, sum = 9, odd

Test	Why
[34,23,1,24,75,33,54,8]	Verifies the first provided example
[99,77,33,66,55]	Verifies the second provided example
[1]	Tests smallest valid array size
[2]	Tests single even digit
[10]	Tests multi-digit number with odd sum
[11]	Tests multi-digit number with even sum
[100]	Tests handling of three-digit values
[50,20,3]	Verifies minimum selection
[88,42,24]	Tests even digit sum for multi-digit minimum
[99,98,97]	Tests larger minimum value
[18,27,36]	Tests odd digit sum case

Edge Cases

A single-element array is an important edge case because the minimum element is automatically the only element. A buggy implementation might assume multiple values exist or accidentally mishandle initialization. Since the algorithm uses min(nums) in Python and initializes from nums[0] in Go, this case works naturally.

Numbers with multiple digits can also be a source of bugs. A naive implementation might incorrectly treat the number as a single value instead of summing individual digits. For example, 33 should produce 3 + 3 = 6, not 33. The repeated modulo and division operations guarantee each digit is processed separately.

Values like 100 are another useful edge case because they contain zeros. A careless implementation might incorrectly stop or ignore internal zeros. Here, digit extraction proceeds correctly: 100 → 10 → 1 → 0, producing a digit sum of 1.

Finally, parity checking itself can be a subtle source of mistakes because the problem uses an unusual return convention: 1 for even and 0 for odd. Many implementations might accidentally reverse this logic. Explicitly checking digit_sum % 2 == 0 avoids confusion and ensures correctness.