Smallest Index With Digit Sum Equal to Index

Smallest Index With Digit Sum Equal to Index - Problem

Array Math Easy

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.

The sum of digits of a number is calculated by adding all its individual digits together. For example, the sum of digits of 123 is 1 + 2 + 3 = 6.

Input & Output

Example 1 — Basic Case

$ Input: nums = [18, 43, 29, 5, 37]

› Output: -1

💡 Note: Check each index: digit_sum(18)=9 ≠ 0, digit_sum(43)=7 ≠ 1, digit_sum(29)=11 ≠ 2, digit_sum(5)=5 ≠ 3, digit_sum(37)=10 ≠ 4. No match found.

Example 2 — Found Match

$ Input: nums = [0, 1, 2, 3, 4, 5]

› Output: 0

💡 Note: At index 0: digit_sum(0) = 0, which equals the index 0. Return 0 as it's the smallest matching index.

Example 3 — Later Match

$ Input: nums = [10, 20, 11, 3]

› Output: 3

💡 Note: Check indices: digit_sum(10)=1 ≠ 0, digit_sum(20)=2 ≠ 1, digit_sum(11)=2 ≠ 2, digit_sum(3)=3 = 3. Return index 3.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers with indices 0, 1, 2, ...

Process

Calculate digit sum for each number and compare with index

Output

Return smallest matching index or -1 if none

Key Takeaway

🎯 Key Insight: We must scan linearly since we need the smallest matching index - no optimization can skip elements

Asked in

G Google 12 M Microsoft 8

The key insight is that we need to find the smallest index where the sum of digits equals the index value. Since we want the smallest index, we must scan from left to right. Best approach is linear scan with digit sum calculation. Time: O(n × d), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Digit Sum Calculation	O(n × d)	O(1)	Same linear scan but with slightly optimized digit sum calculation
Linear Scan with Digit Sum	O(n × d)	O(1)	Iterate through array and calculate digit sum for each number

Optimized Digit Sum Calculation — Algorithm Steps

Step 1: Iterate through array indices
Step 2: Use optimized digit sum calculation
Step 3: Return first matching index
Step 4: Return -1 if no match found

Visualization

Tap to expand

Step-by-Step Walkthrough

Enhanced digit sum

Use optimized calculation to get digit sum

Compare with index

Check if digit sum equals current index

Return result

Return first matching index or -1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int digitSum(int n) {
    if (n == 0) return 0;
    n = abs(n);
    int total = 0;
    while (n) {
        total += n % 10;
        n /= 10;
    }
    return total;
}

int solution(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        if (digitSum(nums[i]) == i) {
            return i;
        }
    }
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × d)

Same as brute force - we still need to check each element and calculate digit sum

✓ Linear Growth

Space Complexity

O(1)

Constant extra space for variables

✓ Linear Space

12.4K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Digit Sum Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler