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;
}
}
Share my 0ms Java code


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 belsd
, 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 higherorder (comparing to the current digit we are considering) digits, we do not know the impact of lowerorder 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 addcomplete
*weight
= 1 * 10 = 10 tocount
. Although the input is 115, what we are dealing with now is 11, the information of lowerorder 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 tocount
.