Problem Description

You are given an integer array nums.

Your task is to find the smallest index i where the sum of digits of the number at that position equals the index itself. In other words, if nums[i] is the number at index i, you need to find the smallest i where:

• The sum of all digits in nums[i] equals i

For example:

• If nums[3] = 12, the sum of digits is 1 + 2 = 3, which equals the index 3
• If nums[5] = 23, the sum of digits is 2 + 3 = 5, which equals the index 5

The solution iterates through the array from index 0 onwards. For each element, it calculates the sum of its digits by repeatedly:

1. Extracting the last digit using modulo operation (x % 10)
2. Adding it to the running sum
3. Removing the last digit by integer division (x //= 10)

Once the digit sum s is calculated for an element at index i, it checks if s == i. If this condition is met, it immediately returns i since we want the smallest such index. If no index satisfies this condition after checking all elements, the function returns -1.

The key insight is that we process the array from left to right, ensuring we find the smallest valid index first.

Intuition

The problem asks for the smallest index where a specific condition is met. This immediately suggests a linear scan from the beginning of the array, since we want the "smallest" index - there's no need for complex algorithms when a simple left-to-right traversal will naturally give us the first (and therefore smallest) valid index.

The core challenge is calculating the sum of digits for each number. We need a way to extract individual digits from a number. The standard approach for this is to use the modulo and division operations:

• x % 10 gives us the last digit of a number
• x // 10 removes the last digit from the number

By repeatedly applying these operations until the number becomes 0, we can extract all digits and sum them up.

Why does this work? Consider the number 345:

• 345 % 10 = 5 (last digit), then 345 // 10 = 34
• 34 % 10 = 4 (second-to-last digit), then 34 // 10 = 3
• 3 % 10 = 3 (first digit), then 3 // 10 = 0 (we stop here)
• Sum = 5 + 4 + 3 = 12

Since we're looking for the smallest index and we're traversing from left to right, we can return immediately upon finding the first index where the digit sum equals the index value. This guarantees we get the smallest valid index without needing to check all elements or store multiple candidates.

If we complete the entire traversal without finding any valid index, we know no such index exists, so we return -1.

Learn more about Math patterns.

Solution Approach

The solution uses a straightforward enumeration approach combined with digit sum calculation. Let's walk through the implementation step by step:

1. Enumerate through the array: We use Python's enumerate() function to iterate through the array, which gives us both the index i and the value x at that index simultaneously:

for i, x in enumerate(nums):

2. Calculate digit sum for each element: For each number x, we initialize a sum variable s = 0 and extract digits one by one:

s = 0
while x:
    s += x % 10  # Add the last digit to sum
    x //= 10     # Remove the last digit

The while x: loop continues as long as x is non-zero. In each iteration:

• x % 10 extracts the rightmost digit
• We add this digit to our running sum s
• x //= 10 performs integer division, effectively removing the rightmost digit

3. Check the condition: After calculating the digit sum s, we check if it equals the current index:

if s == i:
    return i

If the condition is satisfied, we immediately return i. This ensures we get the smallest valid index since we're processing from left to right.

4. Handle the case when no valid index exists: If the loop completes without finding any index where the digit sum equals the index value, we return -1:

return -1

Time Complexity: O(n * m) where n is the length of the array and m is the average number of digits in the elements.

Space Complexity: O(1) as we only use a constant amount of extra space for variables s and the loop variables.

Example Walkthrough

Let's walk through a concrete example with nums = [23, 5, 12, 3, 17].

We need to find the smallest index i where the sum of digits of nums[i] equals i.

Step 1: Check index 0, nums[0] = 23

• Calculate digit sum of 23:
  • 23 % 10 = 3 (extract last digit), sum = 3, remaining = 23 // 10 = 2
  • 2 % 10 = 2 (extract last digit), sum = 3 + 2 = 5, remaining = 2 // 10 = 0
  • Stop (no more digits)
• Digit sum = 5, index = 0
• Is 5 == 0? No, continue

Step 2: Check index 1, nums[1] = 5

• Calculate digit sum of 5:
  • 5 % 10 = 5 (extract last digit), sum = 5, remaining = 5 // 10 = 0
  • Stop (no more digits)
• Digit sum = 5, index = 1
• Is 5 == 1? No, continue

Step 3: Check index 2, nums[2] = 12

• Calculate digit sum of 12:
  • 12 % 10 = 2 (extract last digit), sum = 2, remaining = 12 // 10 = 1
  • 1 % 10 = 1 (extract last digit), sum = 2 + 1 = 3, remaining = 1 // 10 = 0
  • Stop (no more digits)
• Digit sum = 3, index = 2
• Is 3 == 2? No, continue

Step 4: Check index 3, nums[3] = 3

• Calculate digit sum of 3:
  • 3 % 10 = 3 (extract last digit), sum = 3, remaining = 3 // 10 = 0
  • Stop (no more digits)
• Digit sum = 3, index = 3
• Is 3 == 3? Yes! Return 3

We found that at index 3, the digit sum equals the index value, so we return 3. We don't need to check index 4 since we want the smallest valid index.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × d), where n is the length of the array and d is the maximum number of digits in any element of the array. For each element in the array, we iterate through all its digits to calculate the sum. In the worst case, if we consider d as a constant (typically bounded by 10 for 32-bit integers), we can simplify this to O(n).

The space complexity is O(1), as the algorithm only uses a constant amount of extra space regardless of the input size. The variables i, x, and s are the only additional storage used, and they don't scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Condition Check in the Code

The provided code has a critical bug: it checks if digit_sum % 10 == index % 10: instead of if digit_sum == index:. This modulo operation will give incorrect results.

Wrong:

if digit_sum % 10 == index % 10:  # This only compares last digits!
    return index

Correct:

if digit_sum == index:  # Compare the full values
    return index

2. Not Handling Zero Correctly

When nums[i] = 0, the digit sum is 0. The while loop while temp_number > 0: will skip the body entirely, correctly giving digit_sum = 0. However, using while temp_number: could be cleaner but might confuse some developers about the zero case.

Solution: Either explicitly handle zero or add a comment clarifying the behavior:

# Handle zero explicitly for clarity
if number == 0:
    if index == 0:
        return 0
else:
    # Calculate digit sum for non-zero numbers
    while temp_number > 0:
        digit_sum += temp_number % 10
        temp_number //= 10

3. Variable Naming Confusion

Using a temporary variable temp_number while the original number remains unchanged can be confusing. Some might accidentally use number in the while loop, creating an infinite loop.

Better approach: Use the loop variable directly:

for i, x in enumerate(nums):
    s = 0
    while x:
        s += x % 10
        x //= 10
    if s == i:
        return i

4. Not Considering Negative Numbers

If the array could contain negative numbers (though the problem likely assumes non-negative), the modulo operation behaves differently in Python for negative numbers.

Solution: Add validation or handle negative numbers explicitly:

for index, number in enumerate(nums):
    if number < 0:
        continue  # Skip negative numbers
    # ... rest of the logic

5. Early Return Without Full Validation

The code correctly returns on the first match, but developers might mistakenly think they need to find all matches first and then return the minimum.

Clarification: Since we iterate from index 0 onwards, the first match IS the smallest index - no need to collect all matches:

# Correct: Return immediately on first match
for i, x in enumerate(nums):
    if digit_sum == i:
        return i  # This IS the smallest valid index

# Incorrect: Don't do this
valid_indices = []
for i, x in enumerate(nums):
    if digit_sum == i:
        valid_indices.append(i)
return min(valid_indices) if valid_indices else -1  # Unnecessary complexity