3550. Smallest Index With Digit Sum Equal to Index

Array
Math

TIME

O(n * d)

SPACE

O(1)

Intuition

The condition is per-index and independent of everything else, so a single left-to-right scan finds the smallest matching index. Returning on the first match is what makes it smallest.

Approach

For each index i, compute the digit sum of nums[i] by repeatedly taking value % 10 and dividing by 10.
Return i as soon as the digit sum equals i.
Return -1 after the loop.

Complexity

Time: O(n * d) where d <= 4 is the digit count
Space: O(1)

Edge Cases

nums[0] = 0 → digit sum 0 matches index 0, so answer 0
Index 0 with a non-zero value never matches, since every positive number has digit sum at least 1
nums[i] = 1000 → digit sum 1, matches only at index 1
Max digit sum here is 9 + 9 + 9 = 27 (from 999), so indices above 27 can never match; not worth special-casing at n <= 100
No match anywhere → -1 (Example 3)

Code

from typing import List


class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        """
        3550. Smallest Index With Digit Sum Equal to Index
        Time: O(n * d)
        Space: O(1)
        """
        for i, v in enumerate(nums):
            digit_sum = 0
            while v > 0:
                digit_sum += v % 10
                v //= 10
            if digit_sum == i:
                return i
        return -1

/**
 * 3550. Smallest Index With Digit Sum Equal to Index
 * Time: O(n * d)
 * Space: O(1)
 */
class Solution {
    public int smallestIndex(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int v = nums[i];
            int digitSum = 0;
            while (v > 0) {
                digitSum += v % 10;
                v /= 10;
            }
            if (digitSum == i) {
                return i;
            }
        }
        return -1;
    }
}