Scale Engineer

Smallest Index With Digit Sum Equal to Index

Easy
#3161Time: O(N * log M), where N is the length of `nums` and M is the maximum value in `nums`. We iterate through all N elements, and for each element, calculating the digit sum takes O(log M) time.Space: O(K), where K is the number of indices satisfying the condition. In the worst case, all N indices could satisfy the condition, leading to O(N) space complexity for the `validIndices` list.
Patterns
Math
Data structures
Array

Prompt

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:

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:

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:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through the entire array to find all indices that satisfy the given condition. We store these valid indices in a separate list. After checking every element, if we found any valid indices, we return the smallest one from our list. If no such indices were found, we return -1.

Algorithm

  • Initialize an empty list validIndices.
  • Loop through the array nums with index i from 0 to nums.length - 1.
  • Inside the loop, calculate the sum of digits for nums[i].
  • If the digit sum is equal to i, add i to validIndices.
  • After the loop, if validIndices is empty, return -1.
  • Otherwise, return the first element of validIndices.

Walkthrough

The core idea is to not stop at the first match but to find all possible matches and then decide which one is the smallest.

The algorithm proceeds as follows:

  1. Initialize an empty list, for example, validIndices, to store all indices i where the condition sum_of_digits(nums[i]) == i holds true.
  2. Iterate through the input array nums from the first element (i = 0) to the last (i = nums.length - 1).
  3. For each element nums[i], calculate the sum of its digits. A helper function can be used for this. The function would repeatedly take the number modulo 10 (to get the last digit) and add it to a running sum, then divide the number by 10 (to remove the last digit), until the number becomes 0.
  4. Compare the calculated digit sum with the current index i. If they are equal, add the index i to the validIndices list.
  5. After the loop has finished, check if the validIndices list is empty.
  6. If it is empty, it means no index satisfied the condition, so we return -1.
  7. If it's not empty, the smallest index is required. Since we iterated from i=0 upwards, the first element in the list will be the smallest. We return validIndices.get(0).
import java.util.ArrayList;import java.util.List; class Solution {    private int getDigitSum(int n) {        int sum = 0;        while (n > 0) {            sum += n % 10;            n /= 10;        }        return sum;    }     public int smallestEqual(int[] nums) {        List<Integer> validIndices = new ArrayList<>();        for (int i = 0; i < nums.length; i++) {            if (getDigitSum(nums[i]) == i) {                validIndices.add(i);            }        }         if (validIndices.isEmpty()) {            return -1;        } else {            // The first element added will be the smallest index            return validIndices.get(0);        }    }}

Complexity

Time

O(N * log M), where N is the length of `nums` and M is the maximum value in `nums`. We iterate through all N elements, and for each element, calculating the digit sum takes O(log M) time.

Space

O(K), where K is the number of indices satisfying the condition. In the worst case, all N indices could satisfy the condition, leading to O(N) space complexity for the `validIndices` list.

Trade-offs

Pros

  • Conceptually straightforward and easy to implement.

  • Correctly finds all matching indices before selecting the smallest.

Cons

  • Uses unnecessary extra space to store all matching indices.

  • Does not stop early, iterating through the entire array even after the smallest valid index has been found.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem