233. Number of Digit One

  • 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
2
3
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

  1. 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
2
3
4
5
f(9) = 1;
f(99) = f(9) * 10 + 10(contributed by the most significant digit in range [10, 19]) = 20
f(999) = f(99) * 10 + 100(contributed by the most significant digit in range [100, 199]) = 300
f(9999) = f(999) * 10 + 1000(contributed by the most significant digit in range [1000, 1999]) = 10 * 300 + 1000 = 4000
... ...

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
2
3
4
f(2356) += (2356 / 1000) * f(1000 - 1) = 2 * f(999);
f(2356) += (2356 / 1000 > 1 ? 1000 : 0);
f(2356) += (2356 / 1000 == 1 ? 356 + 1 : 0);
f(2356) += f(356);

Below is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int countDigitOne(int n) {
int ans = 0;
if(n <= 0) return 0;
if(n <= 9) return 1;

unordered_map<int, int> mp;
mp[9] = 1;
for(int i = 9; i <= (INT_MAX - 9) / 10; i = i * 10 + 9){
mp[i*10 + 9] = mp[i] * 10 + (i + 1); // mp[99], mp[999], mp[9999], ... ...
}

int nn = n, divisor = 1;
while(nn / 10){
nn /= 10;
divisor *= 10;
}
ans += (n / divisor) * mp[divisor - 1];
ans += (n / divisor > 1) ? divisor : 0;
ans += (n / divisor == 1) ? n % divisor + 1 : 0;
ans += countDigitOne(n % divisor);

return ans;
}
};

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
2
3
4
5
6
int countDigitOne(int n) {
int ones = 0;
for (long long m = 1; m <= n; m *= 10)
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1);
return ones;
}

Explanation

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

1
2
3
4
5
6
7
8
int countDigitOne(int n) {
int ones = 0;
for (long long m = 1; m <= n; m *= 10) {
int a = n/m, b = n%m;
ones += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
}
return ones;
}

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
2
3
4
5
6
public int countDigitOne(int n) {
int ones = 0;
for (long m = 1; m <= n; m *= 10)
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
return ones;
}

Python version

1
2
3
4
5
6
def countDigitOne(self, n):
ones, m = 0, 1
while m <= n:
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1)
m *= 10
return ones

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
2
3
4
5
6
7
8
9
def countDigitOne(self, n):
ones = 0
m = r = 1
while n > 0:
ones += (n + 8) / 10 * m + (n % 10 == 1) * r
r += n % 10 * m
m *= 10
n /= 10
return ones

Java

1
2
3
4
5
6
7
8
9
10
public int countDigitOne(int n) {
int ones = 0, m = 1, r = 1;
while (n > 0) {
ones += (n + 8) / 10 * m + (n % 10 == 1 ? r : 0);
r += n % 10 * m;
m *= 10;
n /= 10;
}
return ones;
}

C++

1
2
3
4
5
6
7
8
9
10
int countDigitOne(int n) {
int ones = 0, m = 1, r = 1;
while (n > 0) {
ones += (n + 8) / 10 * m + (n % 10 == 1) * r;
r += n % 10 * m;
m *= 10;
n /= 10;
}
return ones;
}

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
2
3
(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1 if d == 1
(3) xyz * 1000 + 1000 if d > 1

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

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int countDigitOne(int n) {

if (n <= 0) return 0;
int q = n, x = 1, ans = 0;
do {
int digit = q % 10;
q /= 10;
ans += q * x;
if (digit == 1) ans += n % x + 1;
if (digit > 1) ans += x;
x *= 10;
} while (q > 0);
return ans;

}

// 40 / 40 test cases passed.
// Status: Accepted
// Runtime: 0 ms

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def countDigitOne(self, n):
if n <= 0:
return 0
q, x, ans = n, 1, 0
while q > 0:
digit = q % 10
q /= 10
ans += q * x
if digit == 1:
ans += n % x + 1
elif digit > 1:
ans += x
x *= 10
return ans

# 40 / 40 test cases passed.
# Status: Accepted
# Runtime: 32 ms
# 97.59%

https://discuss.leetcode.com/topic/18068/0ms-o-lgn-accepted-c-solution-using-counting-principle-with-explanation

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int countDigitOne(int n) {
long long int res(0);
int highn(n), lowc(1), lown(0);
while(highn > 0){
int curn = highn % 10;
highn = highn / 10;
if(1 == curn){
//higher: 0~(highn-1); lower: 0 ~ (lowc-1)
res += highn * lowc;
//higher: highn ~ highn; lower:0~lown
res += lown + 1;
}else if(0 == curn){
//curn < 1
//higher: 0~(highn-1); lower: 0 ~ (lowc-1)
res += highn * lowc;
}else{
//curn > 1
res += (highn + 1) * lowc;
}
//update lown and lowc
lown = curn * lowc + lown;
lowc = lowc * 10;
}
return res;
}

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

0 ms recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countDigitOne(int n) {
if(n<1) return 0;
if(n>=1 && n<10) return 1;
// x: first digit
int y=1, x=n;
while(!(x<10)){
x/=10;
y*=10;
}
if(x==1)
return n-y+1+countDigitOne(y-1)+countDigitOne(n%y);
else
return y+x*countDigitOne(y-1)+countDigitOne(n%y);
}
谢谢你,可爱的朋友。