A concise solution accepted as best submission in C, well explained


  • 1

    As long as we have learned permutation and combination in mathematics, we will not try to use brute-force method to hack this one. Before we move any further, tell me how many ones in 9? the answer is 1; there will be 0, 1, 2, 3, ..., 9; in two-digits number 10, 11, ..., 99: for 1 there will be 10, 21, ..., 91 and the number of 1 will be 9; so there will be a simple conclusion:

    • if n = 10, result will be 1 + 1(the second 1 is for the first digit);
    • if n = 100, result will be 10 + 1(the second 1 is for the first digit);
    • if n = 1000, result will be 100 + 1(the second 1 is for the first digit);

    Simply, if n = 200, result will be 210 + 1(the second is for the first digit); if n = 300, result will be 310+1; if n = 400, result will be 410+1; ... , if n = 1000, result will be 1010+1;

    • then how about n = 230? take it apart to 200+30, 200 -> 210+1(the second 1 is for the first digit), 30->31+1(the second 1 is for the first digit);

    Now we've found the secret to dramatically reduce the time cost, traversing each digit instead of from 1 to n which will decrease the time complexity from O(n) to O(logn).

    Equation for each unit will be (m is the unit: 1, 10, 100, 1000...) (n/m+8)/10m+(n/m%10==1)(n%m+1); Very complicated! Yuck! But let's try to take a closer look at this and have an example here to make it easy for you, suppose we have a number 1302193:

    • if m==100, then n/m will be 13021, n%m will be 93; before the fixing hundred-1, there is 1302 which means when we are fixing 1 to hundred position there will be 0, 1, ..., 1301 can be selected before 1 and meantime the part after can be selected from 0, 1, 2, ..., 99 (100 choices can be used); why there is no 1302? we are considering unit 100 -> when hundred-1 fixed, the part after it is not enough for the unit 100 it's only 94 (from 0 to 93) which we will collect also; so the result for hundred-1 will be 1302*100+94;
    • if m==1000, then n/m will be 1302, n%m will be 193; before thousand-2, there is 130 and according combination rules, there will (130+1)100 times occurrences of 1; why 130+1? 2 in thousand position, so fixing thousand 1 in thousand position and before thousand there can be 0-130 choices while after thousand there will be 0-999 -> just a unit 1000; clear? but the left 193 will be ignored unlike the previous situation while the thousand position has 2 instead of 1; so the final result for this unit is 1311000;
    • if m==10000, then n/m will be 13, n%m will be 2193; quite similar, but since ten-thousand position has 0 instead of 2 or bigger digit, so there will be 0-12 choices only before ten-thousand instead of 0-13(unlike the previous example when m==1000 it's 0-130) and since it's not 1 so, the left part 2193 is also useless; so the final result for this unit is 13*10000;

    At last, we reached each unit until n and sum them up, return it.

    Bang. End of story!

    • Space cost O(1)
    • Time cost O(logn)

    int countDigitOne(int n)
    {
        if(n < 10) return 0;
        long long count = 0;
        for(long long m = 1; m <= n; m *= 10)
        {
            int a = n/m;
            int b = n%m;
            count += (a+8)/10*m+(a%10==1)*(b+1); //0, 1 and >=2 should be treated differently when we are counting for each unit;
        }
        return count;
    }

Log in to reply
 

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