3550: Smallest Index With Digit Sum Equal to Index

Difficulty: Easy

Topics: Array Traversal, Digit Manipulation, Precomputation

Companies: Amazon, Microsoft, Bloomberg

Problem Statement

Given an integer array nums, return the smallest index i where the sum of digits of nums[i] equals i. Return -1 if no such index exists.

Example 1

Input: nums = [1,3,2]
Output: 2
Explanation: nums[2] = 2 → digit sum 2

Example 2

Input: nums = [1,10,11]
Output: 1
Explanation: nums[1] = 10 → sum 1 (1+0)

Problem Link: View on LeetCode ↗

Approach 1: Brute Force (Modulo Division)

Iterate through each element, calculate digit sum using modulo operations.

Algorithm Steps

Initialize loop through array indices
For each number, calculate digit sum using modulus 10
Compare sum with current index
Return first matching index

Complexity Analysis

Time Complexity	Space Complexity
O(n*d)	O(1)

Brute Force Solution

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

class Solution {
    public int smallestIndex(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            int sum = 0, n = nums[i];
            while(n > 0) {
                sum += n % 10;
                n /= 10;
            }
            if(sum == i) return i;
        }
        return -1;
    }
}

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

Approach 2: String Conversion Method

Convert numbers to strings for digit sum calculation.

Complexity Analysis

Time Complexity	Space Complexity
O(n*d)	O(d)

String Conversion Solution

class Solution {
public:
    int smallestIndex(vector& nums) {
        for(int i = 0; i < nums.size(); ++i) {
            string s = to_string(nums[i]);
            int sum = 0;
            for(char c : s) sum += c - '0';
            if(sum == i) return i;
        }
        return -1;
    }
};

class Solution {
    public int smallestIndex(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            char[] digits = String.valueOf(nums[i]).toCharArray();
            int sum = 0;
            for(char c : digits) sum += c - '0';
            if(sum == i) return i;
        }
        return -1;
    }
}

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            digit_sum = sum(int(d) for d in str(num))
            if digit_sum == i:
                return i
        return -1

Approach 3: Precomputed Digit Sums

Precompute all possible digit sums for numbers up to 1000.

Complexity Analysis

Time Complexity	Space Complexity
O(n + C)	O(C)

(C = 1001 for numbers 0-1000)

Precomputation Solution

class Solution {
public:
    int smallestIndex(vector& nums) {
        // Precompute digit sums for 0-1000
        vector digitSums(1001, 0);
        for(int i = 0; i <= 1000; ++i) {
            int n = i, sum = 0;
            while(n > 0) {
                sum += n % 10;
                n /= 10;
            }
            digitSums[i] = sum;
        }
        
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] <= 1000 && digitSums[nums[i]] == i)
                return i;
        }
        return -1;
    }
};

class Solution {
    public int smallestIndex(int[] nums) {
        int[] digitSums = new int[1001];
        for(int i = 0; i <= 1000; i++) {
            int n = i, sum = 0;
            while(n > 0) {
                sum += n % 10;
                n /= 10;
            }
            digitSums[i] = sum;
        }
        
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] <= 1000 && digitSums[nums[i]] == i)
                return i;
        }
        return -1;
    }
}

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        # Precompute digit sums
        digit_sums = [0] * 1001
        for i in range(1001):
            digit_sums[i] = sum(int(d) for d in str(i))
        
        for i, num in enumerate(nums):
            if num <= 1000 and digit_sums[num] == i:
                return i
        return -1

Approach Comparison

Approach	Time	Space	Best Use Case
Brute Force (Modulo)	O(n*d)	O(1)	General purpose
String Conversion	O(n*d)	O(d)	Readability
Precomputed	O(n + C)	O(C)	Multiple queries

Optimization Insight: The modulo method provides the best balance of speed and memory usage for single queries.

Edge Cases

1. Zero Handling

Input: [0] → Output: 0 (sum 0 == index 0)

2. Multiple Valid Indices

Input: [1,0,3] → Output: 1 (earliest match)

3. Maximum Input

Input: [999 for _ in range(100)] → Output: 27 (if index 27 exists)

Important: Always check array bounds to prevent index out-of-range errors.

Frequently Asked Questions

Why return the smallest valid index?

The problem specifically requires finding the first occurrence that satisfies the condition.

What's the maximum possible digit sum?

For nums[i] ≤ 1000, maximum sum is 9+9+9=27 (from 999).

Which method is most efficient?

Modulo method has better cache locality and avoids object creation overhead.

How to handle negative numbers?

Problem constraints specify 0 ≤ nums[i] ≤ 1000, so negatives aren't considered.

Can we use recursion for digit sum?

Possible but less efficient due to function call overhead and stack limitations.

Why precompute for 0-1000?

Because the problem constraints limit numbers to 1000, ensuring complete coverage.

How to optimize further?

Early termination on first match makes all approaches O(n) in best case.

What if all elements are invalid?

Return -1 as specified in the problem statement.

Can we use bit manipulation?

Not directly applicable since digit sums require base-10 operations.

How to test edge cases?

Test cases with i=0 matches, large numbers, and all invalid elements.

Final Analysis: The modulo-based brute force method provides the optimal balance of efficiency and readability for this problem, suitable for both small and maximum-sized inputs.