3550. Smallest Index With Digit Sum Equal to Index

Problem Description

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.

Explanation

For each index i in the array nums, calculate the sum of the digits of nums[i]. The goal is to find the smallest index where this digit sum equals the index itself. If there is no index that satisfies this condition, return -1.

For example, if nums = [10, 12, 0, 14]:

At i = 0, sum of digits of nums[0] = 10 is 1 + 0 = 1 (not equal to 0).
At i = 1, sum of digits of nums[1] = 12 is 1 + 2 = 3 (not equal to 1).
At i = 2, sum of digits of nums[2] = 0 is 0 (equal to 2? No).
At i = 3, sum of digits of nums[3] = 14 is 1 + 4 = 5 (not equal to 3).

If no index matches, return -1. Otherwise, return the first index where the match occurs.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, the idea is to check each number in the input array and see if the sum of its digits matches its index. Since the requirement is about matching each element's digit sum to its index, it's natural to simply go through the array from start to finish, calculate the digit sum for each value, and compare it to the current index. If the values match, that's our answer. If not, keep moving through the array until the end. This direct approach works efficiently since we only need a simple loop and digit sum calculations.

Solution Approach

Start by looping through each element in the array nums using its index i. For each number, calculate the sum of its digits. This can be done by repeatedly taking the remainder when dividing by 10 (x % 10) and adding it to a running total, then dividing the number by 10 each time to process the next digit (x //= 10). Once the digit sum is computed, compare it to the current index i:

If the digit sum is equal to i, immediately return i because that's the smallest such index.
If the end of the array is reached and no such index is found, return -1.

This approach uses a simple enumeration of the array and a standard way to compute the digit sum, making it efficient and easy to understand. No extra data structures are needed, as the solution only tracks local variables for the index and sum.

The process can be summarized in pseudocode as follows:

for i, x in enumerate(nums):
    s = 0
    while x:
        s += x % 10
        x //= 10
    if s == i:
        return i
return -1

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example using the array nums = [21, 2, 10, 30]:

At i = 0, nums[0] = 21, sum of digits: 2 + 1 = 3 (not equal to 0).
At i = 1, nums[1] = 2, sum of digits: 2 (equal to 1? No).
At i = 2, nums[2] = 10, sum of digits: 1 + 0 = 1 (equal to 2? No).
At i = 3, nums[3] = 30, sum of digits: 3 + 0 = 3 (equal to 3? Yes).

The smallest index where the sum of the digits equals the index is i = 3. Therefore, the answer is 3.

Solution Implementation

1from typing import List
2
3class Solution:
4    def smallestIndex(self, nums: List[int]) -> int:
5        # Iterate over the list with both index and value
6        for index, value in enumerate(nums):
7            digit_sum = 0
8            temp = value  # Copy of value to extract digits
9            # Calculate the sum of digits of the current number
10            while temp:
11                digit_sum += temp % 10
12                temp //= 10
13            # If the sum of digits matches the index, return index
14            if digit_sum == index:
15                return index
16        # No such index found, return -1
17        return -1
18

1class Solution {
2    public int smallestIndex(int[] nums) {
3        // Iterate through each index of the array
4        for (int i = 0; i < nums.length; ++i) {
5            int sumOfDigits = 0;
6            int currentNum = nums[i]; // Use a separate variable to avoid altering the original array
7
8            // Calculate the sum of digits for currentNum
9            while (currentNum != 0) {
10                sumOfDigits += currentNum % 10;
11                currentNum /= 10;
12            }
13
14            // If the sum of digits equals the index, return the index
15            if (sumOfDigits == i) {
16                return i;
17            }
18        }
19        // If no such index is found, return -1
20        return -1;
21    }
22}
23

1class Solution {
2public:
3    int smallestIndex(std::vector<int>& nums) {
4        // Iterate through each index in the input vector
5        for (int i = 0; i < nums.size(); ++i) {
6            int sumDigits = 0;
7            int currentNum = nums[i];
8
9            // Calculate the sum of the digits of the current number
10            while (currentNum) {
11                sumDigits += currentNum % 10;
12                currentNum /= 10;
13            }
14
15            // Check if the sum of digits equals the current index
16            if (sumDigits == i) {
17                return i; // Return the smallest index that satisfies the condition
18            }
19        }
20        // If no such index is found, return -1
21        return -1;
22    }
23};
24

1/**
2 * Finds the smallest index i in the array where
3 * the sum of digits of nums[i] equals i.
4 * @param nums Array of non-negative integers
5 * @returns The smallest valid index, or -1 if not found
6 */
7function smallestIndex(nums: number[]): number {
8    // Iterate through each index in the nums array
9    for (let i = 0; i < nums.length; ++i) {
10        let sumOfDigits = 0;
11        let value = nums[i];
12
13        // Calculate the sum of digits of value
14        while (value > 0) {
15            sumOfDigits += value % 10;           // Add last digit to sum
16            value = Math.floor(value / 10);      // Remove last digit
17        }
18
19        // Check if the sum of digits equals the current index
20        if (sumOfDigits === i) {
21            return i; // Return the smallest index found
22        }
23    }
24
25    // Return -1 if no such index exists
26    return -1;
27}
28

Time and Space Complexity

The time complexity of the code is O(n * d), where n is the length of the nums array and d is the maximum number of digits in the numbers of nums. This is because, for each element, the code computes the sum of its digits, which takes O(d) time per element.

The space complexity is O(1), as only a constant amount of extra space is used for variables like i, x, and s.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know