Teaching Kids Programming – Confusing Number Validation Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a number N, return true if and only if it is a confusing number, which satisfies the following condition:

We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid. A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.

Example 1:
Input: 6
Output: true
Explanation:
We get 9 after rotating 6, 9 is a valid number and 9!=6.

Example 2:
Input: 89
Output: true
Explanation:
We get 68 after rotating 89, 86 is a valid number and 86!=89.

Example 3:
Input: 11
Output: false
Explanation:
We get 11 after rotating 11, 11 is a valid number but the value remains the same, thus 11 is not a confusing number.

Example 4:
Input: 25
Output: false
Explanation:
We get an invalid number after rotating 25.

Note:
0 <= N <= 10^9
After the rotation we can ignore leading zeros, for example if after rotation we have 0008 then this number is considered as just 8.

Algorithm to Check Confusion Number

We need a function to check if a digit can be rotated 180 and still valid. Returns -1 if it can’t be rotated. Then, by constructing the rotated number, we then can fail when any digit can’t be rotated or the rotated number is the same as the original number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def confusingNumber(self, N: int) -> bool:
        def turn(x):
            if x == 1 or x == 0 or x == 8:
                return x
            if x == 6:
                return 9
            if x == 9:
                return 6
            return -1
        v = ""
        n = str(N)
        for i in n:
            x = turn(int(i))
            if x == -1:
                return False
            v = str(x) + v
        return v != n

class Solution:
    def confusingNumber(self, N: int) -> bool:
        def turn(x):
            if x == 1 or x == 0 or x == 8:
                return x
            if x == 6:
                return 9
            if x == 9:
                return 6
            return -1
        v = ""
        n = str(N)
        for i in n:
            x = turn(int(i))
            if x == -1:
                return False
            v = str(x) + v
        return v != n

Given there are N digits in the original number, the time and space complexity is O(N). We can iterate the digits by also using the following arithmetic method (divide by 10 and get its remainder):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def confusingNumber(self, N: int) -> bool:
        def turn(x):
            if x == 1 or x == 0 or x == 8:
                return x
            if x == 6:
                return 9
            if x == 9:
                return 6
            return -1
        v = 0
        n = N
        while N > 0:
            x = turn(N % 10)
            if x == -1:
                return False
            v = v * 10 + x
            N //= 10
        return v != n

class Solution:
    def confusingNumber(self, N: int) -> bool:
        def turn(x):
            if x == 1 or x == 0 or x == 8:
                return x
            if x == 6:
                return 9
            if x == 9:
                return 6
            return -1
        v = 0
        n = N
        while N > 0:
            x = turn(N % 10)
            if x == -1:
                return False
            v = v * 10 + x
            N //= 10
        return v != n

–EOF (The Ultimate Computing & Technology Blog) —