Maximum Number of Matching Indices After Right Shifts

Problem

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.

Examples

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.

Solution

Method 1 – Brute Force (Digit Sum Check)

Intuition

For each index, check if the sum of the digits of nums[i] equals i. Return the smallest such index, or -1 if none exists.

Approach

1. Iterate through each index i in nums.
2. For each nums[i], compute the sum of its digits.
3. If the sum equals i, return i immediately.
4. If no such index is found, return -1.

Code

C++

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

Go

func smallestIndex(nums []int) int {
    for i, v := range nums {
        s, x := 0, v
        for x > 0 {
            s += x % 10
            x /= 10
        }
        if s == i {
            return i
        }
    }
    return -1
}

Java

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

Kotlin

class Solution {
    fun smallestIndex(nums: IntArray): Int {
        for (i in nums.indices) {
            var x = nums[i]
            var s = 0
            while (x > 0) {
                s += x % 10
                x /= 10
            }
            if (s == i) return i
        }
        return -1
    }
}

Python

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

Rust

impl Solution {
    pub fn smallest_index(nums: Vec<i32>) -> i32 {
        for (i, &v) in nums.iter().enumerate() {
            let mut x = v;
            let mut s = 0;
            while x > 0 {
                s += x % 10;
                x /= 10;
            }
            if s == i as i32 {
                return i as i32;
            }
        }
        -1
    }
}

TypeScript

class Solution {
    smallestIndex(nums: number[]): number {
        for (let i = 0; i < nums.length; i++) {
            let x = nums[i], s = 0;
            while (x > 0) {
                s += x % 10;
                x = Math.floor(x / 10);
            }
            if (s === i) return i;
        }
        return -1;
    }
}

Complexity

• ⏰ Time complexity: O(n * d), where n is the length of nums and d is the number of digits in the largest number.
• 🧺 Space complexity: O(1), as only a few variables are used.