Math
Backtracking
Description
A confusing number is a number that when rotated 180
degrees becomes a different number with each digit valid .
We can rotate digits of a number by 180
degrees to form new digits.
When 0
, 1
, 6
, 8
, and 9
are rotated 180
degrees, they become 0
, 1
, 9
, 8
, and 6
respectively.
When 2
, 3
, 4
, 5
, and 7
are rotated 180
degrees, they become invalid .
Note that after rotating a number, we can ignore leading zeros.
For example, after rotating 8000
, we have 0008
which is considered as just 8
.
Given an integer n
, return the number of confusing numbers in the inclusive range [1, n]
.
Example 1:
Input: n = 20
Output: 6
Explanation: The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.
Example 2:
Input: n = 100
Output: 19
Explanation: The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].
Constraints:
Solutions
Solution 1
Python3 Java C++ Go TypeScript
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 confusingNumberII ( self , n : int ) -> int :
def check ( x : int ) -> bool :
y , t = 0 , x
while t :
t , v = divmod ( t , 10 )
y = y * 10 + d [ v ]
return x != y
def dfs ( pos : int , limit : bool , x : int ) -> int :
if pos >= len ( s ):
return int ( check ( x ))
up = int ( s [ pos ]) if limit else 9
ans = 0
for i in range ( up + 1 ):
if d [ i ] != - 1 :
ans += dfs ( pos + 1 , limit and i == up , x * 10 + i )
return ans
d = [ 0 , 1 , - 1 , - 1 , - 1 , - 1 , 9 , - 1 , 8 , 6 ]
s = str ( n )
return dfs ( 0 , True , 0 )
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 class Solution {
private final int [] d = { 0 , 1 , - 1 , - 1 , - 1 , - 1 , 9 , - 1 , 8 , 6 };
private String s ;
public int confusingNumberII ( int n ) {
s = String . valueOf ( n );
return dfs ( 0 , 1 , 0 );
}
private int dfs ( int pos , int limit , int x ) {
if ( pos >= s . length ()) {
return check ( x ) ? 1 : 0 ;
}
int up = limit == 1 ? s . charAt ( pos ) - '0' : 9 ;
int ans = 0 ;
for ( int i = 0 ; i <= up ; ++ i ) {
if ( d [ i ] != - 1 ) {
ans += dfs ( pos + 1 , limit == 1 && i == up ? 1 : 0 , x * 10 + i );
}
}
return ans ;
}
private boolean check ( int x ) {
int y = 0 ;
for ( int t = x ; t > 0 ; t /= 10 ) {
int v = t % 10 ;
y = y * 10 + d [ v ] ;
}
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
28
29 class Solution {
public :
int confusingNumberII ( int n ) {
string s = to_string ( n );
int d [ 10 ] = { 0 , 1 , -1 , -1 , -1 , -1 , 9 , -1 , 8 , 6 };
auto check = [ & ]( int x ) -> bool {
int y = 0 ;
for ( int t = x ; t ; t /= 10 ) {
int v = t % 10 ;
y = y * 10 + d [ v ];
}
return x != y ;
};
function < int ( int , int , int ) > dfs = [ & ]( int pos , int limit , int x ) -> int {
if ( pos >= s . size ()) {
return check ( x );
}
int up = limit ? s [ pos ] - '0' : 9 ;
int ans = 0 ;
for ( int i = 0 ; i <= up ; ++ i ) {
if ( d [ i ] != -1 ) {
ans += dfs ( pos + 1 , limit && i == up , x * 10 + i );
}
}
return ans ;
};
return dfs ( 0 , 1 , 0 );
}
};
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 func confusingNumberII ( n int ) int {
d := [ 10 ] int { 0 , 1 , - 1 , - 1 , - 1 , - 1 , 9 , - 1 , 8 , 6 }
s := strconv . Itoa ( n )
check := func ( x int ) bool {
y := 0
for t := x ; t > 0 ; t /= 10 {
v := t % 10
y = y * 10 + d [ v ]
}
return x != y
}
var dfs func ( pos int , limit bool , x int ) int
dfs = func ( pos int , limit bool , x int ) ( ans int ) {
if pos >= len ( s ) {
if check ( x ) {
return 1
}
return 0
}
up := 9
if limit {
up = int ( s [ pos ] - '0' )
}
for i := 0 ; i <= up ; i ++ {
if d [ i ] != - 1 {
ans += dfs ( pos + 1 , limit && i == up , x * 10 + i )
}
}
return
}
return dfs ( 0 , true , 0 )
}
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 function confusingNumberII ( n : number ) : number {
const s = n . toString ();
const d : number [] = [ 0 , 1 , - 1 , - 1 , - 1 , - 1 , 9 , - 1 , 8 , 6 ];
const check = ( x : number ) => {
let y = 0 ;
for ( let t = x ; t > 0 ; t = Math . floor ( t / 10 )) {
const v = t % 10 ;
y = y * 10 + d [ v ];
}
return x !== y ;
};
const dfs = ( pos : number , limit : boolean , x : number ) : number => {
if ( pos >= s . length ) {
return check ( x ) ? 1 : 0 ;
}
const up = limit ? parseInt ( s [ pos ]) : 9 ;
let ans = 0 ;
for ( let i = 0 ; i <= up ; ++ i ) {
if ( d [ i ] !== - 1 ) {
ans += dfs ( pos + 1 , limit && i === up , x * 10 + i );
}
}
return ans ;
};
return dfs ( 0 , true , 0 );
}
GitHub