Smallest Index With Digit Sum Equal to Index - Solution & Explanation

Problem Overview: You are given an integer array nums. The task is to find the smallest index i where the digit sum of nums[i] equals the index itself. If no such index exists, return -1. The solution mainly relies on iterating through the array and computing the digit sum of each value.

Approach 1: Enumeration + Digit Sum (O(n · d) time, O(1) space)

Scan the array from left to right and compute the digit sum for every element. For each index i, repeatedly extract digits from nums[i] using modulo and division to calculate its digit sum. Compare the result with the current index. The first index where digitSum(nums[i]) == i is the answer. If the loop completes without a match, return -1. This works because the problem asks specifically for the smallest valid index, so the first match during iteration is guaranteed to be correct.

This approach uses a simple linear traversal over the array. Computing the digit sum of a number with d digits takes O(d) time, which makes the total complexity O(n · d). Since the digit sum calculation uses only a few integer variables, the space complexity remains O(1). The method is straightforward, easy to implement, and performs well because integers typically have a small number of digits.

Approach 2: Incremental Digit Sum Optimization (O(n) time, O(1) space)

If many digit sum calculations are required, you can slightly optimize by using properties of numbers in base‑10. Instead of recomputing the digit sum from scratch each time, maintain a running digit sum as numbers increase and adjust when carries occur (for example when moving from 19 to 20). This reduces repeated digit extraction operations. The core idea still relies on sequential iteration and digit arithmetic from math, but minimizes repeated work.

In practice, the improvement is minor for typical constraints, so most implementations still compute the digit sum directly for clarity. Both versions use constant extra memory and a single pass through the array.

Recommended for interviews: The standard enumeration with digit sum is what interviewers expect. It clearly demonstrates understanding of array traversal and basic number manipulation. Starting with the brute-force digit sum calculation shows correctness first, and discussing incremental digit-sum optimization highlights deeper insight into math properties and performance tradeoffs.