DDSA Solutions

3550. Smallest Index With Digit Sum Equal to Index

EasyView on LeetCode
ArrayMath

Problem Overview

The smallest index is the first one you meet while scanning from the left, so there is no need to collect every match.

Intuition

The smallest index is the first one you meet while scanning from the left, so there is no need to collect every match. A digit sum never exceeds the number, and with values at most 1000 the largest digit sum is 27, so most indexes can be rejected before any division.

Algorithm

  1. 1Stop the scan at index 27, because no later index can equal a digit sum.
  2. 2Skip nums[i] when it is smaller than i.
  3. 3Otherwise add digits with repeated mod 10 and divide by 10.
  4. 4Return i as soon as the digit sum equals i.
  5. 5Return -1 when the limited scan finishes with no match.

Example Walkthrough

Input: nums = [1,10,11]

  1. 1.Index 0 holds 1, and its digit sum is 1, which is not 0.
  2. 2.Index 1 holds 10, and 1+0 equals 1.
  3. 3.That is the smallest match, so index 2 is never needed.

Output: 1

Common Pitfalls

  • •Return the smallest index, not every index that matches.
  • •Digit sum of 0 is 0, so index 0 matches a zero.
  • •Values at most 1000 cannot have a digit sum above 27.
  • •Do not compare the raw value with the index unless the value is smaller than the index, which is only a skip.
3550.cs
C#
// Approach: Walk indexes from the left and return the first i whose digit
// sum equals i. nums[i] is at most 1000, so a digit sum is at most 27 and
// every later index is impossible. A value smaller than i is also impossible,
// because a digit sum never exceeds the number itself.
// Complexity: O(min(n, 28)) digit-sum checks, O(1) extra space.
public class Solution
{
    private const int MaxDigitSum = 27;

    public int SmallestIndex(int[] nums)
    {
        int limit = Math.Min(nums.Length, MaxDigitSum + 1);
        for (int i = 0; i < limit; i++)
        {
            int num = nums[i];
            if (num < i)
                continue;
            if (DigitSum(num) == i)
                return i;
        }
        return -1;
    }

    private static int DigitSum(int num)
    {
        int sum = 0;
        while (num > 0)
        {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}
Was this solution helpful?

Related Problems