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

1
2
3
4

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

1
2
3
4
5
6

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

1
2
3
4

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

Examples

Solution

Method 1 – Linear Scan with Digit Sum Helper

Intuition

For each index, compute the sum of digits of nums[i] and compare to i. Return the first such index, or -1 if none exists.

Approach

  1. Loop through the array.
  2. For each index i, compute the sum of digits of nums[i].
  3. If it equals i, return i. If no such index, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <vector>
using namespace std;
class Solution {
public:
    int smallestIndex(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            int x = nums[i], s = 0;
            while (x) { s += x % 10; x /= 10; }
            if (s == i) return i;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int smallestIndex(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            int x = nums[i], s = 0;
            while (x > 0) { s += x % 10; x /= 10; }
            if (s == i) return i;
        }
        return -1;
    }
}
1
2
3
4
5
6

class Solution:
    def smallestIndex(self, nums):
        for i, x in enumerate(nums):
            if sum(map(int, str(x))) == i:
                return i
        return -1

Complexity

  • ⏰ Time complexity: O(n * d), where n = len(nums), d = max number of digits (at most 4).
  • 🧺 Space complexity: O(1) — No extra space used.