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.