#3550

Easy

LeetCode Problem Workspace

Smallest Index With Digit Sum Equal to Index

Find the smallest index in an array where the sum of the digits equals the index.

Problem Statement

You are given an integer array nums. Return the smallest index i such that the sum of the digits of nums[i] equals i. If no such index exists, return -1.

The sum of the digits for an element is calculated by summing the individual digits of the number. If there is no index that satisfies the condition, return -1.

Examples

Example 1

Input: nums = [1,3,2]

Output: 2

Example 2

Input: nums = [1,10,11]

Output: 1

Example 3

Input: nums = [1,2,3]

Output: -1

Constraints

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

Solution Approach

Iterating through the Array

Start by iterating through each element of the array. For each index, compute the sum of the digits of the number at that index and compare it with the index.

Calculating the Sum of Digits

To calculate the sum of digits, repeatedly divide the number by 10 and add the remainders to the sum. This process can be done using a simple loop.

Return the Smallest Index

If the sum of digits equals the index at any position, return that index immediately. If no such index is found after checking all elements, return -1.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(n), where n is the length of the array, due to the iteration through each element. The space complexity is O(1) because no additional storage is required beyond variables for the sum of digits and the loop index.

What Interviewers Usually Probe

The candidate efficiently calculates the sum of digits for each element.
The candidate checks for matching index and sum of digits correctly.
The candidate can optimize the digit sum calculation for large numbers.

Common Pitfalls or Variants

Common pitfalls

Not calculating the sum of digits correctly.
Failing to return the smallest matching index when there are multiple matches.
Not handling edge cases like when no match exists or the array contains very large numbers.

Follow-up variants

Try using a mathematical formula for digit sum calculation instead of iteration.
Optimize for very large input arrays.
Consider edge cases like when the number at the index is a single digit.

FAQ

What is the approach to solve the 'Smallest Index With Digit Sum Equal to Index' problem?

You can solve this problem by iterating through the array, calculating the sum of digits for each element, and comparing it to the index.

How can I calculate the sum of digits of a number?

You can calculate the sum of digits by repeatedly dividing the number by 10 and adding the remainders to a running total.

What should I do if no index satisfies the condition in the problem?

Return -1 if no index is found where the sum of digits equals the index.

What is the time complexity of solving the 'Smallest Index With Digit Sum Equal to Index' problem?

The time complexity is O(n), where n is the length of the array, because you iterate through each element of the array.

What happens if the array contains very large numbers in this problem?

The algorithm still works, but you should ensure that the digit sum calculation handles large numbers efficiently.

terminal

Solution

Solution 1: Enumeration + Digit Sum

We can start from index $i = 0$ and iterate through each element $x$ in the array, calculating the digit sum $s$ of $x$. If $s = i$, return the index $i$. If no such index is found after traversing all elements, return -1.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#3559 number of ways to assign edge weights ii #3539 find sum of array product of magical sequences #3569 maximize count of distinct primes after split