Math
Dynamic Programming
Description
An integer x
is a good if after rotating each digit individually by 180 degrees, we get a valid number that is different from x
. Each digit must be rotated - we cannot choose to leave it alone.
A number is valid if each digit remains a digit after rotation. For example:
0
, 1
, and 8
rotate to themselves,
2
and 5
rotate to each other (in this case they are rotated in a different direction, in other words, 2
or 5
gets mirrored),
6
and 9
rotate to each other, and
the rest of the numbers do not rotate to any other number and become invalid.
Given an integer n
, return the number of good integers in the range [1, n]
.
Example 1:
Input: n = 10
Output: 4
Explanation: There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.
Example 2:
Input: n = 1
Output: 0
Example 3:
Input: n = 2
Output: 1
Constraints:
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def rotatedDigits ( self , n : int ) -> int :
def check ( x ):
y , t = 0 , x
k = 1
while t :
v = t % 10
if d [ v ] == - 1 :
return False
y = d [ v ] * k + y
k *= 10
t //= 10
return x != y
d = [ 0 , 1 , 5 , - 1 , - 1 , 2 , 9 , - 1 , 8 , 6 ]
return sum ( check ( i ) for i in range ( 1 , 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 class Solution {
private int [] d = new int [] { 0 , 1 , 5 , - 1 , - 1 , 2 , 9 , - 1 , 8 , 6 };
public int rotatedDigits ( int n ) {
int ans = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
if ( check ( i )) {
++ ans ;
}
}
return ans ;
}
private boolean check ( int x ) {
int y = 0 , t = x ;
int k = 1 ;
while ( t > 0 ) {
int v = t % 10 ;
if ( d [ v ] == - 1 ) {
return false ;
}
y = d [ v ] * k + y ;
k *= 10 ;
t /= 10 ;
}
return x != y ;
}
}
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 {
public :
const vector < int > d = { 0 , 1 , 5 , -1 , -1 , 2 , 9 , -1 , 8 , 6 };
int rotatedDigits ( int n ) {
int ans = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
ans += check ( i );
}
return ans ;
}
bool check ( int x ) {
int y = 0 , t = x ;
int k = 1 ;
while ( t ) {
int v = t % 10 ;
if ( d [ v ] == -1 ) {
return false ;
}
y = d [ v ] * k + y ;
k *= 10 ;
t /= 10 ;
}
return x != y ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 func rotatedDigits ( n int ) int {
d := [] int { 0 , 1 , 5 , - 1 , - 1 , 2 , 9 , - 1 , 8 , 6 }
check := func ( x int ) bool {
y , t := 0 , x
k := 1
for ; t > 0 ; t /= 10 {
v := t % 10
if d [ v ] == - 1 {
return false
}
y = d [ v ] * k + y
k *= 10
}
return x != y
}
ans := 0
for i := 1 ; i <= n ; i ++ {
if check ( i ) {
ans ++
}
}
return ans
}
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 class Solution :
def rotatedDigits ( self , n : int ) -> int :
@cache
def dfs ( pos , ok , limit ):
if pos <= 0 :
return ok
up = a [ pos ] if limit else 9
ans = 0
for i in range ( up + 1 ):
if i in ( 0 , 1 , 8 ):
ans += dfs ( pos - 1 , ok , limit and i == up )
if i in ( 2 , 5 , 6 , 9 ):
ans += dfs ( pos - 1 , 1 , limit and i == up )
return ans
a = [ 0 ] * 6
l = 1
while n :
a [ l ] = n % 10
n //= 10
l += 1
return dfs ( l , 0 , 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 class Solution {
private int [] a = new int [ 6 ] ;
private int [][] dp = new int [ 6 ][ 2 ] ;
public int rotatedDigits ( int n ) {
int len = 0 ;
for ( var e : dp ) {
Arrays . fill ( e , - 1 );
}
while ( n > 0 ) {
a [++ len ] = n % 10 ;
n /= 10 ;
}
return dfs ( len , 0 , true );
}
private int dfs ( int pos , int ok , boolean limit ) {
if ( pos <= 0 ) {
return ok ;
}
if ( ! limit && dp [ pos ][ ok ] != - 1 ) {
return dp [ pos ][ ok ] ;
}
int up = limit ? a [ pos ] : 9 ;
int ans = 0 ;
for ( int i = 0 ; i <= up ; ++ i ) {
if ( i == 0 || i == 1 || i == 8 ) {
ans += dfs ( pos - 1 , ok , limit && i == up );
}
if ( i == 2 || i == 5 || i == 6 || i == 9 ) {
ans += dfs ( pos - 1 , 1 , limit && i == up );
}
}
if ( ! limit ) {
dp [ pos ][ ok ] = 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 class Solution {
public :
int a [ 6 ];
int dp [ 6 ][ 2 ];
int rotatedDigits ( int n ) {
memset ( dp , -1 , sizeof dp );
int len = 0 ;
while ( n ) {
a [ ++ len ] = n % 10 ;
n /= 10 ;
}
return dfs ( len , 0 , true );
}
int dfs ( int pos , int ok , bool limit ) {
if ( pos <= 0 ) {
return ok ;
}
if ( ! limit && dp [ pos ][ ok ] != -1 ) {
return dp [ pos ][ ok ];
}
int up = limit ? a [ pos ] : 9 ;
int ans = 0 ;
for ( int i = 0 ; i <= up ; ++ i ) {
if ( i == 0 || i == 1 || i == 8 ) {
ans += dfs ( pos - 1 , ok , limit && i == up );
}
if ( i == 2 || i == 5 || i == 6 || i == 9 ) {
ans += dfs ( pos - 1 , 1 , limit && i == up );
}
}
if ( ! limit ) {
dp [ pos ][ ok ] = 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 func rotatedDigits ( n int ) int {
a := make ([] int , 6 )
dp := make ([][ 2 ] int , 6 )
for i := range a {
dp [ i ] = [ 2 ] int { - 1 , - 1 }
}
l := 0
for n > 0 {
l ++
a [ l ] = n % 10
n /= 10
}
var dfs func ( int , int , bool ) int
dfs = func ( pos , ok int , limit bool ) int {
if pos <= 0 {
return ok
}
if ! limit && dp [ pos ][ ok ] != - 1 {
return dp [ pos ][ ok ]
}
up := 9
if limit {
up = a [ pos ]
}
ans := 0
for i := 0 ; i <= up ; i ++ {
if i == 0 || i == 1 || i == 8 {
ans += dfs ( pos - 1 , ok , limit && i == up )
}
if i == 2 || i == 5 || i == 6 || i == 9 {
ans += dfs ( pos - 1 , 1 , limit && i == up )
}
}
if ! limit {
dp [ pos ][ ok ] = ans
}
return ans
}
return dfs ( l , 0 , true )
}
GitHub