# Java solution with explanation and example

• Explanation:

• Every 10(i.e. div) numbers coutribute 1(i.e. contr) digit1;
• Every 100(i.e. div) numbers coutribute 10(i.e. contr) extra;
• Every 1000(i.e. div) numbers coutribute 100(i.e. contr) extra;
etc.

For example: n = 31500

1. contr=1, div=10, count how many 10 numbers, n/div=3150, contribute 3150*1 digit1, left=n-n/10*10=0, contribute 0;

2. contr=10,div=100, count how many 100 numbers, n/100=315, contribute 315*10 digit1, left=n-n/100*100=0, contribute 0;

3. contr=100,div=1000, count how many 1000 numbers, n/1000=31, contribute 31*100 digit1, left=n-n/1000*1000=500, 500 includes (100-199), therefore the left 500 also constribute 100 digit1;

4. contr=1000,div=10000, count how many 10000 numbers, n/10000=3, contribute 3*1000 digit1, left=n-n/10000*10000=1500, 1500 only includes part of (1000-1999), it constributes 501 digit1;

5. contr=10000,div=100000, count how many 100000 numbers, n/10000=0, contribute 0*1000 digit1, left=n-n/100000*100000=31500, 31500 includes (10000-19999), it constributes 10000 digit1;

6. Done.

``````class Solution {
public int countDigitOne(int n) {
if(n<1) return 0;
long contr=1,res=0;
while(n>=contr){
long div=contr*10,left=n-n/div*div;
res+=n/div*contr+(left>=2*contr?contr:(left>=contr?left%contr+1:0));
contr=div;
}
return (int)res;
}
}
``````

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