Smallest Index With Digit Sum Equal to Index
EasyPrompt
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 indexi = 2. Thus, the output is 2.
Example 2:
Input: nums = [1,10,11]
Output: 1
Explanation:
- For
nums[1] = 10, the sum of digits is1 + 0 = 1, which is equal to indexi = 1. - For
nums[2] = 11, the sum of digits is1 + 1 = 2, which is equal to indexi = 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 <= 1000 <= 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
numswith indexifrom0tonums.length - 1. - Inside the loop, calculate the sum of digits for
nums[i]. - If the digit sum is equal to
i, additovalidIndices. - After the loop, if
validIndicesis 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:
- Initialize an empty list, for example,
validIndices, to store all indicesiwhere the conditionsum_of_digits(nums[i]) == iholds true. - Iterate through the input array
numsfrom the first element (i = 0) to the last (i = nums.length - 1). - 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. - Compare the calculated digit sum with the current index
i. If they are equal, add the indexito thevalidIndiceslist. - After the loop has finished, check if the
validIndiceslist is empty. - If it is empty, it means no index satisfied the condition, so we return
-1. - If it's not empty, the smallest index is required. Since we iterated from
i=0upwards, the first element in the list will be the smallest. We returnvalidIndices.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.
This is the most efficient approach. We can solve the problem in a single pass through the array. We iterate from the beginning of the array (index 0) and check the condition at each index. The first time we find an index i where the sum of digits of nums[i] equals i, we can immediately return that index. Since we are iterating in increasing order of indices, the first one we find is guaranteed to be the smallest.
Algorithm
- Loop through the array
numswith indexifrom0tonums.length - 1. - For each element
nums[i], calculate the sum of its digits. - If the digit sum is equal to the current index
i, returniimmediately. - If the loop finishes without returning, it means no such index was found. Return
-1.
Walkthrough
The problem asks for the smallest index i that satisfies a specific property. This suggests that a linear scan from the beginning of the array is a natural fit. By checking indices 0, 1, 2, ... in order, the first index that meets the criteria will, by definition, be the smallest one. This allows us to stop our search and return the result immediately, making the algorithm efficient.
The algorithm is as follows:
- Iterate through the input array
numswith an indexistarting from0up tonums.length - 1. - For each index
i, calculate the sum of the digits of the numbernums[i]. This can be done with a simple helper function or an inner loop. - To calculate the digit sum of a number
n: initialize asumto 0. Whilenis greater than 0, addn % 10tosumand updatenton / 10. - Compare the calculated digit sum with the current index
i. - If
sum_of_digits(nums[i]) == i, we have found the smallest index that satisfies the condition. We can immediately returni. - If the loop completes without finding any such index, it means no solution exists. In this case, we return
-1after the loop.
class Solution { private int getDigitSum(int n) { int sum = 0; // This loop correctly handles n = 0, resulting in sum = 0. while (n > 0) { sum += n % 10; n /= 10; } return sum; } public int smallestEqual(int[] nums) { for (int i = 0; i < nums.length; i++) { if (getDigitSum(nums[i]) == i) { return i; } } return -1; }}Complexity
Time
O(N * log M), where N is the length of `nums` and M is the maximum value in `nums`. In the worst case, we traverse the entire array. The digit sum calculation for each number takes time proportional to the number of its digits, which is O(log M). Given the constraints, this is effectively O(N).
Space
O(1). We only use a few variables to store the index and the digit sum, which does not depend on the input size.
Trade-offs
Pros
Optimal time complexity as we must check each element in the worst case.
Optimal O(1) space complexity.
Early exit saves computation time if a match is found early in the array.
Cons
No significant cons; this is the ideal solution for the problem as stated.
Solutions
Solution
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; }}class Solution {public: int smallestIndex(vector<int> &nums) { for (int i = 0; i < nums.size(); ++i) { int s = 0; while (nums[i]) { s += nums[i] % 10; nums[i] /= 10; } if (s == i) { return i; } } return -1; }};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 - 1Video 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.