Clean C++ code of log10(N) complexity with detailed explanation


  • 10
    B

    Here's the explanation.
    For each digit d_i:

    1. If di < 1, then the number of 1s on di == factor * (di+1 - 1 + 1). Note the last (+1) is for the case when di+1 is 0, and the (-1) is for that di == 0 for original di+1.

    Eg. For n == 703, there are in total 7 1s on the ten's digit, when the hundred's digit could be (0~6). And for each 1s on the ten's digit, it could appear 10 times when the one's digit varies from (0~9) for each ten.

    1. If di == 1, then the number of 1s on di == factor * (di+1 - 1 + 1) + (number below di + 1).

    Eg. For n == 713, there are in total 7 1s on the ten's digit, when the digit on the hundreds could be (0~6). And for each 1s on the ten's digit, it could appear 4 times when the one's digit varies from (0~3) for each ten.

    1. If di > 1, it's similar to 1), whereas in total 8 1s could be on the ten's digit, when the hundred's digit could be (0~7). So the number of 1s on di == factor * (di+1 + 1).

    Eg. For n == 723, there are in total 8 1s on the ten's digit, when the digit on the hundreds could be (0~7). And for each 1s on the ten's digit, it could appear 10 times when the one's digit varies from (0~9) for each ten.

    • Things in mind:

    There are possibilities where the count/factor might overflow. Use long long instead of int for them.

     class Solution {
        public:
            int countDigitOne(int n) {
                if (n <= 0)
                    return 0;
                
                long long count = 0;    //It may cause integer overflow
                
                long long factor = 1;
                
                while (n / factor) {
                    int lowerNum = n - (n / factor) * factor;
                    int currentDigit = (n / factor) % 10;
                    int higherDigit = n / (factor * 10);
                    
                    switch(currentDigit) {
                        case 0:
                            count += higherDigit * factor;
                            break;
                        case 1:
                            count += higherDigit * factor + (lowerNum + 1);
                            break;
                        default:
                            count += (higherDigit + 1) * factor;
                    }
                    
                    factor *= 10;
                }
                
                return count;
            }
        };

  • 0

    You can use the <sub>1</sub> tag to identify 1 as a subscript.


  • 0
    Z

    If count is gonna overflow in some cases, then long long still get cast to an int when returning (as the function returning type is INT), so it overflows anyway.


  • 0
    B

    Thanks for the tips, updated:)


  • 0
    B

    That's true...But using int won't pass some of the test cases.


  • 0
    H

    I think the last sentence of the second bullet has small error in description even the code is right:

    "2) If di == 1, then the number of 1s on di == factor * (di+1 - 1 + 1) + (number below di + 1).

    Eg. For n == 713, there are in total 7 1s on the ten's digit, when the digit on the hundreds could be (0~6). And for each 1s on the ten's digit, it could appear 4 times when the one's digit varies from (0~3) for each ten."

    Original:
    "And for each 1s on the ten's digit, it could appear 4 times when the one's digit varies from (0~3) for each ten."

    Could be:
    And when the hundred's digit is 7, and the ten's digit is 1, it has only 4 times for the one's digit which varies from (0~3).


Log in to reply
 

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