Number of Digit One

https://leetcode.com/problems/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.

Solution. The solution is to iterate each digit. Each time, split the digit into 3 parts and do calculation. For example, if n = 320456. When we iterate to mid = 0. Left part is 32, right part is 456. Let’s fix 1 and count combination of left and right. Left can iterate from 0 ~ 31, totally 32 times. Right part iterates from 0 to 999, totally 1000 times.

So first part is ans = 32 * 1000.

Then let’s analyze when left part is 32.

Since mid == 0, for left part plus mid == 1(for 32), there is no chance to iterate right part.

If n = 321456. Since mid == 1, so totally, when left part plus mid == 1(for 32), right part can iterate from 0 to 456, totally 457.

If n = 322456. Since mid  > 1, so totally, when left part plus mid == 1(for 321), right part can iterate from 0 to 999, totally 1000.

When writing the code, we should loop k = 1 to k <= n.

/*
For n = 54321, k = 1, 10, 100, 1000, 10000
 when k = 100, should divide into 54, 3, 21
 l = 543,
 m = 543 % 100 = 3
 r = 54321 - 543 * 100 = 21
 l = 543 / 10 = 543
*/
public int countDigitOne(int n) {
    int ans = 0;
    for (long k = 1; k <= n; k *= 10) {
        long left = n / k;
        long mid = left % 10;
        long right = n - left * k;
        left = left / 10;
        ans += left * k;
        if (mid > 1) {
            ans += k;
        }
        else if (mid == 1) {
            ans += right + 1;
        }
    }
    return ans;
}

Check my code on github link.