# Smallest Index With Digit Sum Equal to Index
**Difficulty:** EASY
[External](https://leetcode.com/problems/smallest-index-with-digit-sum-equal-to-index)
Canonical: https://scaleengineer.com/dsa/problems/smallest-index-with-digit-sum-equal-to-index
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
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:**

* For `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:**

* For `nums[1] = 10`, the sum of digits is `1 + 0 = 1`, which is equal to index `i = 1`.
* For `nums[2] = 11`, the sum of digits is `1 + 1 = 2`, which is equal to index `i = 2`.
* Since index 1 is the smallest, the output is 1.

**Example 3:**

**Input:** nums = \[1,2,3\]

**Output:** \-1

**Explanation:**

* Since no index satisfies the condition, the output is -1.

**Constraints:**

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 1000`

# Approaches
## Brute-Force with List Storage
This approach involves iterating through the entire array to find all indices that satisfy the given condition. We store these valid indices in a separate list. After checking every element, if we found any valid indices, we return the smallest one from our list. If no such indices were found, we return -1.
**Time:** O(N * log M), where N is the length of `nums` and M is the maximum value in `nums`. We iterate through all N elements, and for each element, calculating the digit sum takes O(log M) time. · **Space:** O(K), where K is the number of indices satisfying the condition. In the worst case, all N indices could satisfy the condition, leading to O(N) space complexity for the `validIndices` list.
**Pros:** Conceptually straightforward and easy to implement.; Correctly finds all matching indices before selecting the smallest.
**Cons:** Uses unnecessary extra space to store all matching indices.; Does not stop early, iterating through the entire array even after the smallest valid index has been found.
### Explanation
The core idea is to not stop at the first match but to find all possible matches and then decide which one is the smallest.

The algorithm proceeds as follows:
1.  Initialize an empty list, for example, `validIndices`, to store all indices `i` where the condition `sum_of_digits(nums[i]) == i` holds true.
2.  Iterate through the input array `nums` from the first element (`i = 0`) to the last (`i = nums.length - 1`).
3.  For each element `nums[i]`, calculate the sum of its digits. A helper function can be used for this. The function would repeatedly take the number modulo 10 (to get the last digit) and add it to a running sum, then divide the number by 10 (to remove the last digit), until the number becomes 0.
4.  Compare the calculated digit sum with the current index `i`. If they are equal, add the index `i` to the `validIndices` list.
5.  After the loop has finished, check if the `validIndices` list is empty.
6.  If it is empty, it means no index satisfied the condition, so we return `-1`.
7.  If it's not empty, the smallest index is required. Since we iterated from `i=0` upwards, the first element in the list will be the smallest. We return `validIndices.get(0)`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private int getDigitSum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public int smallestEqual(int[] nums) {
        List<Integer> validIndices = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (getDigitSum(nums[i]) == i) {
                validIndices.add(i);
            }
        }

        if (validIndices.isEmpty()) {
            return -1;
        } else {
            // The first element added will be the smallest index
            return validIndices.get(0);
        }
    }
}
```
### Algorithm
- Initialize an empty list `validIndices`.
- Loop through the array `nums` with index `i` from `0` to `nums.length - 1`.
- Inside the loop, calculate the sum of digits for `nums[i]`.
- If the digit sum is equal to `i`, add `i` to `validIndices`.
- After the loop, if `validIndices` is empty, return `-1`.
- Otherwise, return the first element of `validIndices`.

## Optimal Single Pass Linear Scan
This is the most efficient approach. We can solve the problem in a single pass through the array. We iterate from the beginning of the array (index 0) and check the condition at each index. The first time we find an index `i` where the sum of digits of `nums[i]` equals `i`, we can immediately return that index. Since we are iterating in increasing order of indices, the first one we find is guaranteed to be the smallest.
**Time:** O(N * log M), where N is the length of `nums` and M is the maximum value in `nums`. In the worst case, we traverse the entire array. The digit sum calculation for each number takes time proportional to the number of its digits, which is O(log M). Given the constraints, this is effectively O(N). · **Space:** O(1). We only use a few variables to store the index and the digit sum, which does not depend on the input size.
**Pros:** Optimal time complexity as we must check each element in the worst case.; Optimal O(1) space complexity.; Early exit saves computation time if a match is found early in the array.
**Cons:** No significant cons; this is the ideal solution for the problem as stated.
### Explanation
The problem asks for the *smallest* index `i` that satisfies a specific property. This suggests that a linear scan from the beginning of the array is a natural fit. By checking indices `0, 1, 2, ...` in order, the first index that meets the criteria will, by definition, be the smallest one. This allows us to stop our search and return the result immediately, making the algorithm efficient.

The algorithm is as follows:
1.  Iterate through the input array `nums` with an index `i` starting from `0` up to `nums.length - 1`.
2.  For each index `i`, calculate the sum of the digits of the number `nums[i]`. This can be done with a simple helper function or an inner loop.
3.  To calculate the digit sum of a number `n`: initialize a `sum` to 0. While `n` is greater than 0, add `n % 10` to `sum` and update `n` to `n / 10`.
4.  Compare the calculated digit sum with the current index `i`.
5.  If `sum_of_digits(nums[i]) == i`, we have found the smallest index that satisfies the condition. We can immediately return `i`.
6.  If the loop completes without finding any such index, it means no solution exists. In this case, we return `-1` after the loop.

```java
class Solution {
    private int getDigitSum(int n) {
        int sum = 0;
        // This loop correctly handles n = 0, resulting in sum = 0.
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public int smallestEqual(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (getDigitSum(nums[i]) == i) {
                return i;
            }
        }
        return -1;
    }
}
```
### Algorithm
- Loop through the array `nums` with index `i` from `0` to `nums.length - 1`.
- For each element `nums[i]`, calculate the sum of its digits.
- If the digit sum is equal to the current index `i`, return `i` immediately.
- If the loop finishes without returning, it means no such index was found. Return `-1`.

# Solutions
### Java

```java
class Solution {
public
  int smallestIndex(int[] nums) {
    for (int i = 0; i < nums.length; ++i) {
      int s = 0;
      while (nums[i] != 0) {
        s += nums[i] % 10;
        nums[i] /= 10;
      }
      if (s == i) {
        return i;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int smallestIndex(vector<int> &nums) {
    for (int i = 0; i < nums.size(); ++i) {
      int s = 0;
      while (nums[i]) {
        s += nums[i] % 10;
        nums[i] /= 10;
      }
      if (s == i) {
        return i;
      }
    }
    return -1;
  }
};

```

### Python

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

```