Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

I find the problem not so easy to understand. Here are some thoughts: We know that for every 10 numbers, there is one digit 1 on single digit. And for every 100 numbers, there are 10 digit 1 on tens digit, and so on. For number greater than 10, when the current digit is greater than 2, we know all 10 ones for current digit is included. For example, for 23, 10 to 19 are included, so for the tens digit, there are 10 ones. What if the current digit equals to 1? For example, if n = 16. Then for tens digit, we need to add 16 % 10 + 1 = 7 ones.

So the idea is iteratively calculate how many ones we need for each digit and add them up.

public int countDigitOne(int n) {
    
        long rst = 0;
        for (long digit = 1; digit <= n; digit *= 10) {
            long first = n / digit, second = n % digit;
            rst += (first + 8) / 10 * digit;
            if (first % 10 == 1)
                rst += (second + 1);
        }
        return (int)rst;
    }