My Java solution 0ms with explanation, easy to understand


  • 0

    My idea is to count every digit 1 at every digits.
    At each step, First calculate the maximum number of 1 it can get,
    and then deduct the excessive 1 it gets.

    Take 13 for example:
    Start from units,
    max = (13+9)/10 * 1 = 2 <--- 1, 11
    temp = 10-(8+13%10+1) = -2 <--- it indicates that we don't have to deduct anything.

    tens,
    max = (13+90)/100 * 10 = 10 <--- 10,11,12,13,14,15,16,17,18,19
    temp = 100 - (80+13%100+1) = 6 <-- so we have to deduct 6(14,15,16,17,18,19).

    public int countDigitOne(int n) {
           long i=1;
           long sum=0;
           for(int j=0;j<10;j++){
               sum += (n+9*i)/(i*10) * i;
               long temp = 2*i-(n%(i*10))-1; // or long temp = 10*i-(8i+n%(i*10)+1)
               if(temp<i && temp >0)sum -=temp;
               i*=10;
           }
           return (int)sum;
    }
    

Log in to reply
 

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