Math
Dynamic Programming
Description
We call a positive integer special if all of its digits are distinct .
Given a positive integer n
, return the number of special integers that belong to the interval [1, n]
.
Example 1:
Input: n = 20
Output: 19
Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
Example 2:
Input: n = 5
Output: 5
Explanation: All the integers from 1 to 5 are special.
Example 3:
Input: n = 135
Output: 110
Explanation: There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.
Constraints:
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 class Solution :
def countSpecialNumbers ( self , n : int ) -> int :
def A ( m , n ):
return 1 if n == 0 else A ( m , n - 1 ) * ( m - n + 1 )
vis = [ False ] * 10
ans = 0
digits = [ int ( c ) for c in str ( n )[:: - 1 ]]
m = len ( digits )
for i in range ( 1 , m ):
ans += 9 * A ( 9 , i - 1 )
for i in range ( m - 1 , - 1 , - 1 ):
v = digits [ i ]
j = 1 if i == m - 1 else 0
while j < v :
if not vis [ j ]:
ans += A ( 10 - ( m - i ), i )
j += 1
if vis [ v ]:
break
vis [ v ] = True
if i == 0 :
ans += 1
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 class Solution {
public int countSpecialNumbers ( int n ) {
List < Integer > digits = new ArrayList <> ();
while ( n != 0 ) {
digits . add ( n % 10 );
n /= 10 ;
}
int m = digits . size ();
int ans = 0 ;
for ( int i = 1 ; i < m ; ++ i ) {
ans += 9 * A ( 9 , i - 1 );
}
boolean [] vis = new boolean [ 10 ] ;
for ( int i = m - 1 ; i >= 0 ; -- i ) {
int v = digits . get ( i );
for ( int j = i == m - 1 ? 1 : 0 ; j < v ; ++ j ) {
if ( vis [ j ] ) {
continue ;
}
ans += A ( 10 - ( m - i ), i );
}
if ( vis [ v ] ) {
break ;
}
vis [ v ] = true ;
if ( i == 0 ) {
++ ans ;
}
}
return ans ;
}
private int A ( int m , int n ) {
return n == 0 ? 1 : A ( m , n - 1 ) * ( m - n + 1 );
}
}
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 class Solution {
public :
int countSpecialNumbers ( int n ) {
int ans = 0 ;
vector < int > digits ;
while ( n ) {
digits . push_back ( n % 10 );
n /= 10 ;
}
int m = digits . size ();
vector < bool > vis ( 10 );
for ( int i = 1 ; i < m ; ++ i ) {
ans += 9 * A ( 9 , i - 1 );
}
for ( int i = m - 1 ; ~ i ; -- i ) {
int v = digits [ i ];
for ( int j = i == m - 1 ? 1 : 0 ; j < v ; ++ j ) {
if ( ! vis [ j ]) {
ans += A ( 10 - ( m - i ), i );
}
}
if ( vis [ v ]) {
break ;
}
vis [ v ] = true ;
if ( i == 0 ) {
++ ans ;
}
}
return ans ;
}
int A ( int m , int n ) {
return n == 0 ? 1 : A ( m , n - 1 ) * ( m - n + 1 );
}
};
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 func countSpecialNumbers ( n int ) int {
digits := [] int {}
for n != 0 {
digits = append ( digits , n % 10 )
n /= 10
}
m := len ( digits )
vis := make ([] bool , 10 )
ans := 0
for i := 1 ; i < m ; i ++ {
ans += 9 * A ( 9 , i - 1 )
}
for i := m - 1 ; i >= 0 ; i -- {
v := digits [ i ]
j := 0
if i == m - 1 {
j = 1
}
for ; j < v ; j ++ {
if ! vis [ j ] {
ans += A ( 10 - ( m - i ), i )
}
}
if vis [ v ] {
break
}
vis [ v ] = true
if i == 0 {
ans ++
}
}
return ans
}
func A ( m , n int ) int {
if n == 0 {
return 1
}
return A ( m , n - 1 ) * ( m - n + 1 )
}
Solution 2
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
26
27 class Solution :
def countSpecialNumbers ( self , n : int ) -> int :
return self . f ( n )
def f ( self , n ):
@cache
def dfs ( pos , mask , lead , limit ):
if pos <= 0 :
return lead ^ 1
up = a [ pos ] if limit else 9
ans = 0
for i in range ( up + 1 ):
if ( mask >> i ) & 1 :
continue
if i == 0 and lead :
ans += dfs ( pos - 1 , mask , lead , limit and i == up )
else :
ans += dfs ( pos - 1 , mask | 1 << i , 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
45 class Solution {
private int [] a = new int [ 11 ] ;
private int [][] dp = new int [ 11 ][ 1 << 11 ] ;
public int countSpecialNumbers ( int n ) {
return f ( n );
}
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 mask , boolean lead , boolean limit ) {
if ( pos <= 0 ) {
return lead ? 0 : 1 ;
}
if ( ! lead && ! limit && dp [ pos ][ mask ] != - 1 ) {
return dp [ pos ][ mask ] ;
}
int up = limit ? a [ pos ] : 9 ;
int ans = 0 ;
for ( int i = 0 ; i <= up ; ++ i ) {
if ((( mask >> i ) & 1 ) == 1 ) {
continue ;
}
if ( i == 0 && lead ) {
ans += dfs ( pos - 1 , mask , lead , limit && i == up );
} else {
ans += dfs ( pos - 1 , mask | 1 << i , false , limit && i == up );
}
}
if ( ! lead && ! limit ) {
dp [ pos ][ mask ] = 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 class Solution {
public :
int a [ 11 ];
int dp [ 11 ][ 1 << 11 ];
int countSpecialNumbers ( int n ) {
return f ( n );
}
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 mask , bool lead , bool limit ) {
if ( pos <= 0 ) {
return lead ? 0 : 1 ;
}
if ( ! lead && ! limit && dp [ pos ][ mask ] != -1 ) {
return dp [ pos ][ mask ];
}
int up = limit ? a [ pos ] : 9 ;
int ans = 0 ;
for ( int i = 0 ; i <= up ; ++ i ) {
if (( mask >> i ) & 1 ) continue ;
if ( i == 0 && lead ) {
ans += dfs ( pos - 1 , mask , lead , limit && i == up );
} else {
ans += dfs ( pos - 1 , mask | 1 << i , false , limit && i == up );
}
}
if ( ! lead && ! limit ) {
dp [ pos ][ mask ] = 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
52
53 func countSpecialNumbers ( n int ) int {
return f ( n )
}
func f ( n int ) int {
a := make ([] int , 11 )
dp := make ([][] int , 11 )
for i := range dp {
dp [ i ] = make ([] int , 1 << 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 , mask int , lead , limit bool ) int {
if pos <= 0 {
if lead {
return 0
}
return 1
}
if ! lead && ! limit && dp [ pos ][ mask ] != - 1 {
return dp [ pos ][ mask ]
}
ans := 0
up := 9
if limit {
up = a [ pos ]
}
for i := 0 ; i <= up ; i ++ {
if (( mask >> i ) & 1 ) == 1 {
continue
}
if i == 0 && lead {
ans += dfs ( pos - 1 , mask , lead , limit && i == up )
} else {
ans += dfs ( pos - 1 , mask | 1 << i , false , limit && i == up )
}
}
if ! lead && ! limit {
dp [ pos ][ mask ] = ans
}
return ans
}
return dfs ( l , 0 , true , true )
}
GitHub