# 0ms recursive solution in c++ (8 line code)

• The idea is check number of 1 for each 10,100,1000,10000 ... position. For example, for 312:

check 000~099, 100~199, 200~299, 300~312 and sum them up, for 000~099 and 200~299, it's countDigitOne(99), for 100~199 it's 100+countDigitOne(99), and for 300~312 it's countDigitOne(12).

``````int countDigitOne(int n, int x){
if(n == 0) return 0;
if(n<10 || x==1) return 1;
if(n/x == 1) return n-n/x*x+1+countDigitOne(n-n/x*x)+countDigitOne(x-1);
return x+n/x*countDigitOne(x-1)+countDigitOne(n-n/x*x);
}

int countDigitOne(int n) {
if(n <= 0) return 0;
int x = 1, y=n;
for(;y>=10;x*=10,y/=10);
return countDigitOne(n, x);
}``````

• why 100~199 is 100+countDigitOne(99)? not 100? 100~199 is 100 numbers,and they all contain digit one.

• This problem asks for total number of 1 in all positive int below n, rather than number of positive int below n which contains 1. 100~199 contains 100 digit 1 at hundred position. We also need to count number of digit 1 at 10's position and 1's position. So we need to add countDigitOne(99)

• Inspired by yours idea

``````def countDigitOne(self, n):
if n < 0:
return 0
i = 1
j = n
while j >= 10:
i *= 10
j /= 10
return self.count(n, i)

def count(self, n, x):
if n == 0 and x == 1:
return 0
elif n < 10 and x == 1:
return 1
elif n/x == 1:
return self.countDigitOne(x-1) + (1+n%x) + self.countDigitOne(n%x)
else:
return x + (n/x)*self.countDigitOne(x-1) + self.countDigitOne(n%x)``````

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