LeetCode 3550 - Smallest Index With Digit Sum Equal to Index

LeetCode Problem 3550

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

This problem asks us to find the smallest index i in an integer array nums such that the sum of the digits of nums[i] equals i. In other words, for each element in the array, we compute the sum of its digits and check whether that sum matches the element's index. If multiple indices satisfy this condition, we return the smallest one. If no index satisfies the condition, we return -1.

The input nums is an integer array with length between 1 and 100. Each element is between 0 and 1000. These constraints indicate that the array is small, and each number is also small enough to efficiently compute the sum of its digits. There is no need for advanced optimizations like prefix sums or digit dynamic programming.

Important edge cases include numbers with multiple digits, zeros, the smallest or largest possible array size, and cases where no index satisfies the condition.

Approaches

The brute-force approach is straightforward: iterate through the array, compute the sum of digits for each number, and compare it with the current index. If they match, return the index immediately. If no match is found after checking all elements, return -1. This approach is correct because it examines every element and applies the required condition exactly as specified. Given the small input size (maximum 100 elements, digits sum up to at most 1 + 0 + 0 + 0 = 1,000), this approach is fast enough.

The key observation that leads to the optimal solution is that the brute-force method is already optimal for this problem because the array is small, and each digit sum calculation is inexpensive. There are no intermediate results or complex data structures required. Thus, the "optimal" solution is essentially the same as the brute-force solution, but implemented efficiently and clearly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * d)	O(1)	Iterate through the array, sum digits (d = number of digits ≤ 4)
Optimal	O(n * d)	O(1)	Same as brute-force; direct computation is sufficient for constraints

Algorithm Walkthrough

1. Initialize a loop over all indices i from 0 to len(nums) - 1.
2. For each nums[i], compute the sum of its digits. This can be done by repeatedly taking modulo 10 and dividing by 10, or by converting it to a string and summing the integer values of the characters.
3. Compare the digit sum with the current index i.
4. If the digit sum equals i, immediately return i as this is the smallest such index.
5. If the loop completes without finding a match, return -1.

Why it works: The algorithm checks every index sequentially, ensuring that the first index meeting the condition is returned. Since indices are checked in ascending order, the smallest index is guaranteed.

Python Solution

from typing import List

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            digit_sum = sum(int(d) for d in str(num))
            if digit_sum == i:
                return i
        return -1

The Python implementation iterates through the array using enumerate to access both index and value. The digit sum is calculated by converting the number to a string and summing its individual digits. The equality check ensures that we return the first index that satisfies the condition. If no index satisfies the condition, -1 is returned.

Go Solution

func smallestIndex(nums []int) int {
    for i, num := range nums {
        sum := 0
        temp := num
        for temp > 0 {
            sum += temp % 10
            temp /= 10
        }
        if sum == i {
            return i
        }
    }
    return -1
}

In Go, we use a traditional for loop with range to iterate over indices and values. The digit sum is computed using integer arithmetic (modulo and division) instead of string conversion. The rest of the logic mirrors the Python solution.

Worked Examples

Example 1: nums = [1,3,2]

i	nums[i]	digit sum	digit sum == i?
0	1	1	No
1	3	3	No
2	2	2	Yes

Return 2.

Example 2: nums = [1,10,11]

i	nums[i]	digit sum	digit sum == i?
0	1	1	No
1	10	1	Yes

Return 1 (smallest index).

Example 3: nums = [1,2,3]

i	nums[i]	digit sum	digit sum == i?
0	1	1	No
1	2	2	No
2	3	3	No

Return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * d)	Iterate over n elements, computing digit sum for each (d ≤ 4)
Space	O(1)	Only a few integer variables are used; no extra data structures

The small value of d (number of digits in each number) ensures that even a naive sum-of-digits computation is efficient.

Test Cases

# Provided examples
assert Solution().smallestIndex([1,3,2]) == 2  # sum matches at index 2
assert Solution().smallestIndex([1,10,11]) == 1  # smallest index is 1
assert Solution().smallestIndex([1,2,3]) == -1  # no index matches

# Edge cases
assert Solution().smallestIndex([0]) == 0  # digit sum 0 matches index 0
assert Solution().smallestIndex([1000]) == -1  # digit sum 1 != index 0
assert Solution().smallestIndex([0,1,2,3,4,5,6,7,8,9]) == 0  # first index 0 matches
assert Solution().smallestIndex([19,28,37,46,55,64,73,82,91]) == -1  # sums never equal index

Test	Why
[1,3,2]	Checks a simple middle match
[1,10,11]	Checks multiple matches, returns smallest index
[1,2,3]	Checks no match case
[0]	Single element, matches index 0
[1000]	Single element, sum does not match index 0
[0,1,2,...,9]	Multiple elements, first index matches
[19,28,...]	Multiple elements, no matches

Edge Cases

The first edge case is an array of length 1, where the single number is either zero or greater than zero. This tests if the algorithm correctly handles the smallest array and computes digit sum properly.

The second edge case is an array containing numbers with multiple digits, including leading zeros in the computation if we use string conversion. For example, 10 or 1000 must correctly sum digits as 1 and 1 respectively.

The third edge case is an array where no index satisfies the condition. This ensures that the algorithm correctly returns -1 instead of failing or returning an incorrect index. The loop iterates completely and correctly handles the "no match" scenario.