Math
Dynamic Programming
Description
Given a single-digit integer d
and two integers low
and high
, return the number of times that d
occurs as a digit in all integers in the inclusive range [low, high]
.
Example 1:
Input: d = 1, low = 1, high = 13
Output: 6
Explanation: The digit d = 1 occurs 6 times in 1, 10, 11, 12, 13.
Note that the digit d = 1 occurs twice in the number 11.
Example 2:
Input: d = 3, low = 100, high = 250
Output: 35
Explanation: The digit d = 3 occurs 35 times in 103,113,123,130,131,...,238,239,243.
Constraints:
0 <= d <= 9
1 <= low <= high <= 2 * 108
Solutions
Solution 1
Python3 Java C++ Go
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 class Solution :
def digitsCount ( self , d : int , low : int , high : int ) -> int :
return self . f ( high , d ) - self . f ( low - 1 , d )
def f ( self , n , d ):
@cache
def dfs ( pos , cnt , lead , limit ):
if pos <= 0 :
return cnt
up = a [ pos ] if limit else 9
ans = 0
for i in range ( up + 1 ):
if i == 0 and lead :
ans += dfs ( pos - 1 , cnt , lead , limit and i == up )
else :
ans += dfs ( pos - 1 , cnt + ( i == d ), False , limit and i == up )
return ans
a = [ 0 ] * 11
l = 0
while n :
l += 1
a [ l ] = n % 10
n //= 10
return dfs ( l , 0 , True , True )
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 class Solution {
private int d ;
private int [] a = new int [ 11 ] ;
private int [][] dp = new int [ 11 ][ 11 ] ;
public int digitsCount ( int d , int low , int high ) {
this . d = d ;
return f ( high ) - f ( low - 1 );
}
private int f ( int n ) {
for ( var e : dp ) {
Arrays . fill ( e , - 1 );
}
int len = 0 ;
while ( n > 0 ) {
a [++ len ] = n % 10 ;
n /= 10 ;
}
return dfs ( len , 0 , true , true );
}
private int dfs ( int pos , int cnt , boolean lead , boolean limit ) {
if ( pos <= 0 ) {
return cnt ;
}
if ( ! lead && ! limit && dp [ pos ][ cnt ] != - 1 ) {
return dp [ pos ][ cnt ] ;
}
int up = limit ? a [ pos ] : 9 ;
int ans = 0 ;
for ( int i = 0 ; i <= up ; ++ i ) {
if ( i == 0 && lead ) {
ans += dfs ( pos - 1 , cnt , lead , limit && i == up );
} else {
ans += dfs ( pos - 1 , cnt + ( i == d ? 1 : 0 ), false , limit && i == up );
}
}
if ( ! lead && ! limit ) {
dp [ pos ][ cnt ] = ans ;
}
return ans ;
}
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 class Solution {
public :
int d ;
int a [ 11 ];
int dp [ 11 ][ 11 ];
int digitsCount ( int d , int low , int high ) {
this -> d = d ;
return f ( high ) - f ( low - 1 );
}
int f ( int n ) {
memset ( dp , -1 , sizeof dp );
int len = 0 ;
while ( n ) {
a [ ++ len ] = n % 10 ;
n /= 10 ;
}
return dfs ( len , 0 , true , true );
}
int dfs ( int pos , int cnt , bool lead , bool limit ) {
if ( pos <= 0 ) {
return cnt ;
}
if ( ! lead && ! limit && dp [ pos ][ cnt ] != -1 ) {
return dp [ pos ][ cnt ];
}
int up = limit ? a [ pos ] : 9 ;
int ans = 0 ;
for ( int i = 0 ; i <= up ; ++ i ) {
if ( i == 0 && lead ) {
ans += dfs ( pos - 1 , cnt , lead , limit && i == up );
} else {
ans += dfs ( pos - 1 , cnt + ( i == d ), false , limit && i == up );
}
}
if ( ! lead && ! limit ) {
dp [ pos ][ cnt ] = ans ;
}
return ans ;
}
};
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 func digitsCount ( d int , low int , high int ) int {
f := func ( n int ) int {
a := make ([] int , 11 )
dp := make ([][] int , 11 )
for i := range dp {
dp [ i ] = make ([] int , 11 )
for j := range dp [ i ] {
dp [ i ][ j ] = - 1
}
}
l := 0
for n > 0 {
l ++
a [ l ] = n % 10
n /= 10
}
var dfs func ( int , int , bool , bool ) int
dfs = func ( pos , cnt int , lead , limit bool ) int {
if pos <= 0 {
return cnt
}
if ! lead && ! limit && dp [ pos ][ cnt ] != - 1 {
return dp [ pos ][ cnt ]
}
up := 9
if limit {
up = a [ pos ]
}
ans := 0
for i := 0 ; i <= up ; i ++ {
if i == 0 && lead {
ans += dfs ( pos - 1 , cnt , lead , limit && i == up )
} else {
t := cnt
if d == i {
t ++
}
ans += dfs ( pos - 1 , t , false , limit && i == up )
}
}
if ! lead && ! limit {
dp [ pos ][ cnt ] = ans
}
return ans
}
return dfs ( l , 0 , true , true )
}
return f ( high ) - f ( low - 1 )
}
GitHub