0ms o(lgn) accepted c++ solution using counting principle with explanation


  • 28
    T

    For every digit in n (Suppose n = 240315, the digits are 2, 4, 0, 3, 1, 5),I respectively count the number of digit 1 assuming the position of current digit is 1 and other digits of n is arbitrary.

    For example, I select 3 in n as the current digit, and I suppose the position of 3 is 1.

    The highn is the number composed with the digits before the current digit. In the example, highn = 240;

    The lown is the number composed with the digits after the current digit. In the example, lown = 15.

    The lowc = 10 ^ (the number of lower digits). In the example, lowc = 100;

    As curn = 3 and curn > 1, (highn * 10 + 1) must be less than (highn * 10 + curn). Then the higher part can be 0 ~ highn, the lower part can be 0 ~ (lowc-1), and the current result = (highn + 1) * lowc.

    int countDigitOne(int n) {
            long long int res(0);
            int highn(n), lowc(1), lown(0);
            while(highn > 0){
                int curn = highn % 10;
                highn = highn / 10;
                if(1 == curn){
                    //higher: 0~(highn-1);  lower:  0 ~ (lowc-1)
                    res += highn * lowc;
                    //higher: highn ~ highn;     lower:0~lown
                    res += lown + 1;
                }else if(0 == curn){  
                    //curn < 1
                   //higher: 0~(highn-1);  lower:  0 ~ (lowc-1)
                    res += highn * lowc;
                }else{              
                    //curn > 1
                    res += (highn + 1) * lowc;
                }
                //update lown and lowc
                lown = curn * lowc + lown;
                lowc = lowc * 10;
            }
            return res;
        }

  • 0

    Nice code using counting principle


  • 0
    T

    Thank you! ^_^


  • 0
    Y

    Nice analysis!
    Problem 1:
    When input is 1, the output should be 1. From your code, the output I get is 0.
    When input is 12, the output should be 4, because 1, 11, 10. From your code, the output I get is 2.

    Problem 2:
    When you're counting 2, 4, 0, (1), 1, 5, I believe you take 111(1)11 into account.
    When you're counting 2, 4, 0, 3, (1), 5, you take 1111(1)1 into account again.

    Please let me know if I misunderstood you. I'm not good at math.


  • 0
    T

    Answer 1.1: When input is 1, the higher part can only be 0. As curn == 1, hign * lowc = 0. But res = lown+1 = 0 + 1 = 1, not output 0. In the special case, the lower part is viewed as only a zero. (higher: highn ~ highn; lower:0~lown) -->> (higher: 0~ 0; lower:0~0). so, the output is 1.


  • 0
    T

    Answer 1.2.1: For the digit 2, highn = 1, lown = 0, lowc =1. As curn > 1, the higher part can be 0~highn, namely 0~1; the lower part can be 0~(lowc-1), namely(0~0), so the number of 1 is 2*1 = 2. In fact, the two number is 0(1) and 1(1) .


  • 0
    T

    Answer 1.2.2: For the digit 1, highn=0, lown=2,lowc=10. As curn==1, if the higher part is 0~(highn-1), the higher part is already less than the input n, so the lower part can be 0~(lowc-1). But 0~(highn-1) -->> 0~(-1), this case is impossible. Only the second case is possible, namely the higher part is (highn ~ highn) -->(0 ~ 0). In the second case, the higher part is equal to the higher part of the input n. So, the lower part must be less than the lower part of the input n, and the lower part can be 0~lown --> 0~2. the number of 1 is 1*3 = 3. In fact, the three number is (1)0 , (1)1 and (1)2. Finally, the output of my code is 2 +3 = 5.


  • 0
    T

    Answer 2: yes, my code takes 111111 into account for 6 times. But for every time, I only plus 1 into the final result, not plus 6.


Log in to reply
 

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