# Easy to understand python solution, can generalized to 0 to 9

• ``````class Solution(object):
def countDigitOne(self, n):
"""
:type n: int
:rtype: int
"""
if n < 1:
return 0
result = 0
# number of appearances for one cycle when 1 appears at position i
i = 1
while n >= i:
# complete cycle, one more complete cycle if current digit > 1
cycle = n / (i * 10) + (1 if n / i % 10 > 1 else 0)
result += cycle * i
# incomplete cycle if current digit == 1
if n / i % 10 == 1:
result += n % i + 1
i *= 10
return result
``````

A cycle is 0~9 for one position. 1 appears a certain number of times in each cycle.

For example, given number 32107.

At position 7, 1 appears 3210 complete cycles, and within each cycle 1 appears once. Also, because 7 > 1, so it can be regarded as one more complete cycle. In total 1 appears 3211 times at position 7.

At position 0, 1 appears 321 complete cycles, and within each cycle 1 appears 10 times, eg, ...10-...19. In total 1 appears 321 * 10 times at position 0.

At position 1, 32 complete cycles, and within each cycle 1 appears 100 times, eg, ..100-..199. Notice here it is 1, so it has incomplete cycle from 32100-32107, which is 32107 % 100 + 1 = 8 times. In total 1 appears 32 * 100 + 8 times at position 1.

So on so forth.

A generalized code for any digit 0 ~ 9 is below.

• This post is deleted!

• ``````class Solution(object):
def countDigitOne(self, n):
"""
:type n: int
:rtype: int
"""
def countDigitX(x, n):
if n < x:
return 0
result = 0
# number of appearances for one cycle when x appears at position i
i = 1
while n >= i:
# complete cycle, one more complete cycle if current digit > x
cycle = n / (i * 10) + (1 if n / i % 10 > x else 0)
result += cycle * i
# incomplete cycle if current digit == x
if n / i % 10 == x:
result += n % i + 1
i *= 10
return result
return countDigitX(1, n)
``````

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