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

• 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;
}
};``````

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

• 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.

• Thanks for the tips, updated:)

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

• 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).

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