Smallest Index With Digit Sum Equal to Index

Difficulty: Easy | Acceptance: 80.20% | Paid: No Topics: Array, Math

Given a 0-indexed integer array nums, return the smallest index i such that the sum of the digits of i is equal to nums[i]. If there is no such index, return -1.

The sum of the digits of a number is defined as the sum of all its individual digits. For example, the sum of the digits of 123 is 1 + 2 + 3 = 6.

• Examples
• Constraints
• Linear Scan
• Precomputation

Examples

Input: nums = [0,1,2]
Output: 0
Explanation:
i = 0: The sum of the digits of 0 is 0, which is equal to nums[0].
i = 1: The sum of the digits of 1 is 1, which is equal to nums[1].
i = 2: The sum of the digits of 2 is 2, which is equal to nums[2].
The smallest index satisfying the condition is 0.

Input: nums = [4,3,2,1]
Output: 2
Explanation:
i = 0: The sum of the digits of 0 is 0, which is not equal to nums[0] (4).
i = 1: The sum of the digits of 1 is 1, which is not equal to nums[1] (3).
i = 2: The sum of the digits of 2 is 2, which is equal to nums[2].
The smallest index satisfying the condition is 2.

Input: nums = [1,2,3]
Output: -1
Explanation:
No index i satisfies the condition that the sum of the digits of i equals nums[i].

Constraints

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

Linear Scan

Intuition We iterate through the array indices from 0 to n-1. For each index, we calculate the sum of its digits and compare it with the value at that index in the array. The first index that satisfies the condition is our answer.

Steps

• Iterate through the array using index i from 0 to nums.length - 1.
• For each i, calculate the sum of its digits.
• If the calculated sum equals nums[i], return i immediately.
• If the loop completes without finding a match, return -1.

class Solution:
    def smallestIndex(self, nums: list[int]) -> int:
        def digit_sum(x: int) -> int:
            s = 0
            while x:
                s += x % 10
                x //= 10
            return s

        for i in range(len(nums)):
            if digit_sum(i) == nums[i]:
                return i
        return -1

Complexity

• Time: O(n · log₁₀ n) — We iterate through n indices, and for each index i, the digit sum calculation takes O(log₁₀ i) time.
• Space: O(1) — We only use a constant amount of extra space for variables.
• Notes: This is the most optimal approach as we stop as soon as we find the first valid index.

Precomputation

Intuition Instead of calculating the digit sum on the fly for every index during the comparison, we can precompute the digit sums for all possible indices (0 to n-1) first. Then, we simply iterate and compare the precomputed values with the array values.

Steps

• Initialize an array digitSums of size n.
• Iterate from 0 to n-1, calculating the digit sum for each index and storing it in digitSums.
• Iterate through the array again. If digitSums[i] == nums[i], return i.
• If no match is found, return -1.

class Solution:
    def smallestIndex(self, nums: list[int]) -> int:
        n = len(nums)
        digit_sums = [0] * n
        
        for i in range(n):
            s = 0
            x = i
            while x:
                s += x % 10
                x //= 10
            digit_sums[i] = s
            
        for i in range(n):
            if digit_sums[i] == nums[i]:
                return i
                
        return -1

Complexity

• Time: O(n · log₁₀ n) — We iterate through n indices twice, and digit sum calculation takes O(log₁₀ i) time.
• Space: O(n) — We use an extra array of size n to store the digit sums.
• Notes: This approach trades space for a potential (though negligible in this case) separation of computation and lookup. It is less space-efficient than the Linear Scan.