Share my readable C++ and python Simple Solution with only 0ms and 36ms

• compute a list with the number of 1s less than the power of 10
• for example:
• in C++, I build a vector:{0: 0, 1: 0, 10: 1, 100: 20, 1000:
300},means that there are 300 1s less than pow(10,3)
• in Python, I built a dict that {0: 0, 1: 0, 10: 1, 100: 20, 1000:
300},means that there are 300 1s less than 1000

My C++ Solution:

``````    int countDigitOne(int n) {
if (n <= 0)
return 0;
int bits = 0, res = 0;

while(n >= pow(10,bits))
bits ++;
vector<int>flag(bits,0);
for(int i=1;i < bits; i++)
flag[i] = flag[i-1]*10 + pow(10,i-1);
int temp = pow(10,bits-1);
while(n >= 10){
int foo = n/temp;
if (foo > 1)
res += temp;
else if(foo == 1)
res += (n%temp + 1);
res += foo * flag[bits-1];
bits --;
n = n % temp;
temp = temp/10;
}
if(n>=1)
res ++;
return res;
}
``````

My Python Solution:

``````    def countDigitOne(self, n):
bits = 0
dic = {0:0,1:0,10:1}
res = 0
if n <= 0:
return 0
while n >= 10**bits:
bits += 1
temp = 10**(bits - 1)
for i in range(1,bits):
dic[10**i] = dic[10**(i - 1)] * 10 + 10**(i-1)
print dic
while n >= 10:
x = n/temp
if x > 1:
res += (temp)
elif x == 1:
res += (n % temp +1)
res += x*(dic[temp])
n = n % temp
temp /= 10
if n >= 1:
res += 1
return res``````

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