Watch 5 video solutions for Smallest Index With Digit Sum Equal to Index, a easy level problem involving Array, Math. This walkthrough by CodeJulian has 1,714 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
Return the smallest index i such that the sum of the digits of nums[i] is equal to i.
If no such index exists, return -1.
Example 1:
Input: nums = [1,3,2]
Output: 2
Explanation:
nums[2] = 2, the sum of digits is 2, which is equal to index i = 2. Thus, the output is 2.Example 2:
Input: nums = [1,10,11]
Output: 1
Explanation:
nums[1] = 10, the sum of digits is 1 + 0 = 1, which is equal to index i = 1.nums[2] = 11, the sum of digits is 1 + 1 = 2, which is equal to index i = 2.Example 3:
Input: nums = [1,2,3]
Output: -1
Explanation:
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 1000Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumeration + Digit Sum | O(n · d) | O(1) | Best general solution. Simple scan of the array with digit extraction for each number. |
| Incremental Digit Sum Optimization | O(n) | O(1) | When many digit sums must be computed and avoiding repeated digit extraction improves performance. |