LeetCode 3550 - Smallest Index With Digit Sum Equal to Index

LeetCode Problem 3550

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem requires us to find the smallest index in an integer array nums such that the sum of the digits of the element at that index is equal to the index itself. In other words, for each index i, we calculate the sum of the digits of nums[i] and check if it equals i. If multiple indices satisfy this condition, we return the smallest one. If no index satisfies the condition, we return -1.

The input, nums, is a list of integers between 0 and 1000, and its length ranges from 1 to 100. This means the array is small enough to allow a straightforward linear scan. Each element's digit sum can be calculated quickly because the maximum value is 1000, which has at most four digits.

Important edge cases include:

• Arrays where no index satisfies the condition, e.g., [1,2,3].
• Arrays where multiple indices satisfy the condition, requiring selection of the smallest.
• Arrays containing 0, as its digit sum is 0, which may match index 0.

Approaches

The brute-force approach is straightforward: iterate through every index of nums, compute the sum of digits for each element, and check if it equals the index. Since we are guaranteed that the array length is at most 100 and numbers are at most 1000, this approach is efficient in practice. It gives the correct answer because it directly checks the condition for every index.

A slightly more optimal approach leverages the fact that numbers are small (≤1000), but for this problem, no significant optimization beyond the linear scan is required. The brute-force method is effectively optimal because we must examine each element to ensure we find the smallest valid index.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * d) where d is number of digits (max 4)	O(1)	Iterate through all elements, compute digit sum, return smallest index
Optimal	O(n * d)	O(1)	Same as brute force; constraints are small, so linear scan is sufficient

Algorithm Walkthrough

1. Start from index i = 0 and iterate through each element of the array nums.
2. For each nums[i], calculate the sum of its digits. This can be done by repeatedly extracting the last digit using modulo 10 and integer division by 10.
3. Compare the sum of digits with the current index i.
4. If the sum equals the index, immediately return i since we are looking for the smallest index.
5. If the iteration completes without finding any such index, return -1.

Why it works: The algorithm guarantees correctness because it examines indices in increasing order and returns the first one that satisfies the digit sum condition. This ensures that the smallest index is returned. Each digit sum calculation is exact and exhaustive.

Python Solution

from typing import List

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            digit_sum = 0
            temp = num
            while temp > 0:
                digit_sum += temp % 10
                temp //= 10
            if digit_sum == i:
                return i
        return -1

The Python implementation uses a simple for loop with enumerate to access both index and value. The inner while loop calculates the sum of digits by repeatedly extracting the last digit and adding it to digit_sum. If a match is found, we return immediately; otherwise, we return -1 at the end.

Go Solution

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

In Go, the logic is almost identical. The main differences are syntactic: range provides both index and value, and the % and / operators are used to calculate the sum of digits. The function returns -1 if no valid index is found.

Worked Examples

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

i	nums[i]	digit sum	condition met?
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	condition met?
0	1	1	No
1	10	1	Yes

Return 1 (smallest index).

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

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

Return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * d)	We iterate through n elements, each with at most d digits (d ≤ 4).
Space	O(1)	Only a few variables are used; no additional data structures.

Even in the worst case, the algorithm is extremely fast due to small constraints.

Test Cases

# provided examples
assert Solution().smallestIndex([1,3,2]) == 2  # matches last index
assert Solution().smallestIndex([1,10,11]) == 1  # smallest index
assert Solution().smallestIndex([1,2,3]) == -1  # no match

# boundary tests
assert Solution().smallestIndex([0]) == 0  # digit sum 0 matches index 0
assert Solution().smallestIndex([1000]) == 1  # sum 1 does not match index 0, returns -1
assert Solution().smallestIndex([0,1,2,3,4,5,6,7,8,9]) == 0  # first element matches

# stress tests
assert Solution().smallestIndex(list(range(100))) == 0  # first index 0 always matches 0
assert Solution().smallestIndex([10,11,12,13,14]) == 1  # 10's digit sum matches index 1

Test	Why
[1,3,2]	Checks last index match
[1,10,11]	Checks smallest index among multiple matches
[1,2,3]	Checks no match scenario
[0]	Edge case where index 0 matches
[1000]	Edge case with largest allowed value
range(100)	Large array with guaranteed match at index 0
[10,11,12,13,14]	Small numbers with early match

Edge Cases

Single-element array: Arrays of length 1, like [0] or [1], test whether the implementation handles minimal input correctly. The algorithm correctly computes the digit sum and returns the index if it matches.

Element equals 0: When nums[i] is 0, the digit sum is 0, which may match index 0. A naive implementation that assumes non-zero digits could fail here, but our loop correctly returns 0.

Multiple matches: Arrays like [1,10,11] have multiple indices satisfying the condition. A proper solution must return the smallest index, not the largest or last match. Our linear scan guarantees the first valid index is returned.