- 28.5%

https://leetcode.com/problems/number-of-digit-one/#/description

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

1 | For example: |

Hint:

- Beware of overflow.

剑指offer 52

方法一：

https://discuss.leetcode.com/topic/41642/easy-to-understand-c-0ms-solution-with-detailed-explanation

Easy to understand C++ 0ms solution with detailed explanation

We start from basics:

1 | f(9) = 1; |

How about 23?

1 | 23 = [0, 9] + [10, 19] + [20, 23] |

[10, 19] can be reduced to solve f(9) + 10, because its most significant digit is 1. And [20, 23] can be reduced to solve f(3) + 0, because the most significant digit is 2, so this digit doesn’t contribute to final result.

So now we know

1 | f(23) = f(9) * 2 + 10 + f(3) |

So now when we look at a number n (e.g. 2356), we look at the most significant digit(2), its divisor with highest 10’s power (1000), and its remainder (356), try to reduce to a smaller number iteratively.

(1) Since most significant digit is 2, so we know range [0, 999], [1000, 1999] are included, so we add 2 * f(999).

(2) Also, since we have [1000, 1999] covered, we should add extra 1000.

(3) Then we look at range [2000, 2356], try to reduce it to [0, 356] by dropping most significant digit 2, it doesn’t impact the final result since most significant digit is 2 not 1.

(4) Finally, we add f(356)

So eventually, we have

1 | f(2356) += (2356 / 1000) * f(1000 - 1) = 2 * f(999); |

Below is the code:

1 | class Solution { |

https://discuss.leetcode.com/topic/18054/4-lines-o-log-n-c-java-python

4+ lines, O(log n), C++/Java/Python

Go through the digit positions one at a time, find out how often a “1” appears at each position, and sum those up.

C++ solution

1 | int countDigitOne(int n) { |

Explanation

Let me use variables a and b to make the explanation a bit nicer.

1 | int countDigitOne(int n) { |

Go through the digit positions by using position multiplier m with values 1, 10, 100, 1000, etc.

For each position, split the decimal representation into two parts, for example split n=3141592 into a=31415 and b=92 when we’re at m=100 for analyzing the hundreds-digit. And then we know that the hundreds-digit of n is 1 for prefixes “” to “3141”, i.e., 3142 times. Each of those times is a streak, though. Because it’s the hundreds-digit, each streak is 100 long. So (a / 10 + 1) * 100 times, the hundreds-digit is 1.

Consider the thousands-digit, i.e., when m=1000. Then a=3141 and b=592. The thousands-digit is 1 for prefixes “” to “314”, so 315 times. And each time is a streak of 1000 numbers. However, since the thousands-digit is a 1, the very last streak isn’t 1000 numbers but only 593 numbers, for the suffixes “000” to “592”. So (a / 10 * 1000) + (b + 1) times, the thousands-digit is 1.

The case distincton between the current digit/position being 0, 1 and >=2 can easily be done in one expression. With (a + 8) / 10 you get the number of full streaks, and a % 10 == 1 tells you whether to add a partial streak.

Java version

1 | public int countDigitOne(int n) { |

Python version

1 | def countDigitOne(self, n): |

Using sum or recursion it can also be a one-liner.

Old solution

Go through the digit positions from back to front. I found it ugly to explain, so I made up that above new solution instead. The n here is the new solution’s a, and the r here is the new solution’s b+1.

Python

1 | def countDigitOne(self, n): |

Java

1 | public int countDigitOne(int n) { |

C++

1 | int countDigitOne(int n) { |

https://discuss.leetcode.com/topic/27565/java-python-one-pass-solution-easy-to-understand

Java/Python one pass solution easy to understand

The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example

1 | if n = xyzdabc |

and we are considering the occurrence of one on thousand, it should be:

1 | (1) xyz * 1000 if d == 0 |

iterate through all digits and sum them all will give the final answer

Java

1 | public int countDigitOne(int n) { |

Python

1 | def countDigitOne(self, n): |

0ms o(lgn) accepted c++ solution using counting principle with explanation

For every digit in n (Suppose n = 240315, the digits are 2, 4, 0, 3, 1, 5)，I respectively count the number of digit 1 assuming the position of current digit is 1 and other digits of n is arbitrary.

For example, I select 3 in n as the current digit, and I suppose the position of 3 is 1.

The highn is the number composed with the digits before the current digit. In the example, highn = 240;

The lown is the number composed with the digits after the current digit. In the example, lown = 15.

The lowc = 10 ^ (the number of lower digits). In the example, lowc = 100;

As curn = 3 and curn > 1, (highn * 10 + 1) must be less than (highn * 10 + curn). Then the higher part can be 0 ~ highn, the lower part can be 0 ~ (lowc-1), and the current result = (highn + 1) * lowc.

1 | int countDigitOne(int n) { |

https://discuss.leetcode.com/topic/22441/0-ms-recursive-solution

0 ms recursive solution

1 | int countDigitOne(int n) { |