# Share my O(lgn) C++ solution to Number of Digit One

• share my O(lgn) solution :

``````class Solution {
public:
int countDigitOne(int n) {
long long base = 1, res = 0, last = 0;
while(n >= base){
int index = (n / base) % 10;
long long remain = n - (n / base) * base;
if(index > 1){
res = res + index * last + base;
}else if(index == 1){
res = res + index * last + remain + 1;
}else{
res = res + index * last;
}
last = last * 10 + base;
base = base * 10;
}
return res;
}
};
``````

Follow Up: you can change the code to meet the new problem `Number of Digit K`, such as `Number of Digit 3`

``````class Solution {
public:
int countDigitK(int n, int k) {
long long base = 1, res = 0, last = 0;
while(n >= base){
int index = (n / base) % 10;
long long remain = n - (n / base) * base;
if(index > k){
res = res + index * last + base;
}else if(index == k){
res = res + index * last + remain + 1;
}else{
res = res + index * last;
}
last = last * 10 + base;
base = base * 10;
}
return res;
}
};``````

• Why the variable type of 'base' ,'res','last' must use long long? In the meanwhile the input variable type is int.

• @John Actually, only the variable type of 'base' must be long long. For example, if the `n == INT_MAX`, the value of base can be 10,000,000,000, which is overflow when base is int, so the judgement of `while(n >= base)` will be wrong.

• I guess it's better to change "remain = n - (n / base) * base" to "remain = n % base".

• @ ljian3377 Yeah, that looks like more simple

• can anyone explain the logic behind it

• why "last = last * 10 + base" ?

• did you know yet why last=last*10 +base

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