# Share my 0ms Java code

• ``````public class Solution {
public int countDigitOne(int n) {
if (n <= 0) {
return 0;
}
int count = 0;
int copyN = n;
for (int weight = 1; n > 0; weight *= 10) {
int complete = n / 10;
int lsb = n % 10;
if (lsb < 1) {
count += weight * complete;
} else if (lsb > 1) {
count += weight * (complete + 1);
} else {  // lsb == 1
count += weight * complete + copyN % weight + 1;
}
n = complete;
}
return count;
}
}``````

• Your algorithm is amazing, but I can't figure it out. Could you give me some more detail?

• Thank you. I count the 1s digit by digit, which is the reason why `weight` | `n` is scaling up | down by a factor of 10. `complete` means how many "complete cycles" are there for the current digit. `lsb` means Least Significant Bit (my mistake here, should be `lsd`, that is, Least Significant Digit, not Bit).

Example 1. 20, `lsb` = 0, `complete` = 20 / 10 = 2, which means we have (0)1, 11, there are 2 ones at the 10^0 digit.

Example 2. 135, `lsb` = 5, `complete` = 135 / 10 = 13, which means not only we have (0)1, 11, 21, 31,..., 121, also we have 131, there are 14 ones at the 10^0 digit.

Example 3. 131, `lsb` = 1, `complete` = 131 / 10 = 13, which means we have (0)1, 11, 21, 31,..., 121 and 131, a total of 14 ones at the 10^0 digit. It seems that this is identical with the previous case, however, `n` keeps scaling down by a factor of 10,which means we can only know the impact of higher-order (comparing to the current digit we are considering) digits, we do not know the impact of lower-order digits.

Example 4. 115, currently, we consider the 10^1 digit, so `weight` = 10. `n` = 11, `lsb` = 1, `complete` = 11 / 10 = 1, which means we have (0)1. Considering this is 10^1 digit, each of them actually stands for 10, 11,..., 19, so we should add `complete` * `weight` = 1 * 10 = 10 to `count`. Although the input is 115, what we are dealing with now is 11, the information of lower-order digits is lost, that is the "5" in 115 is lost. `copyN` reminds us of the lost information. `copyN % weight + 1` adds 110, 111,..., 115, a total of 6 ones at the 10^1 digit to `count`.

• Thank you so much. I have got it with your examples, which makes it easy for me.

• Are you Chinese? 你是中国人 吗？

• yes i am.......

• This post is deleted!

• You are't China now, right?

• nah. in california. just a mediocore software developer :p

top developers usually don't come to leetcode.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.