Problem

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 ofgood integers in the range _[1, n].

Examples

Example 1

1
2
3
4

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

1
2

Input: n = 1
Output: 0

Example 3

1
2

Input: n = 2
Output: 1

Constraints

  • 1 <= n <= 10^4

Solution

Method 1 - DP or Brute Force

Intuition

A number is good if it contains at least one digit that changes (2,5,6,9) and all digits are valid after rotation (0,1,2,5,6,8,9). We can check each number up to n, or use DP to speed up.

Approach

  1. For each number from 1 to n:
    • For each digit, check if it’s valid (in {0,1,2,5,6,8,9}).
    • If any digit is in {2,5,6,9}, mark as good.
    • If all digits valid and at least one changes, count it.

Code

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

class Solution {
public:
    int rotatedDigits(int n) {
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            int x = i, good = 0, valid = 1;
            while (x) {
                int d = x % 10;
                if (d == 3 || d == 4 || d == 7) { valid = 0; break; }
                if (d == 2 || d == 5 || d == 6 || d == 9) good = 1;
                x /= 10;
            }
            if (valid && good) ++res;
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func rotatedDigits(n int) int {
    res := 0
    for i := 1; i <= n; i++ {
        x, valid, good := i, true, false
        for x > 0 {
            d := x % 10
            if d == 3 || d == 4 || d == 7 { valid = false; break }
            if d == 2 || d == 5 || d == 6 || d == 9 { good = true }
            x /= 10
        }
        if valid && good { res++ }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int rotatedDigits(int n) {
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            int x = i;
            boolean valid = true, good = false;
            while (x > 0) {
                int d = x % 10;
                if (d == 3 || d == 4 || d == 7) { valid = false; break; }
                if (d == 2 || d == 5 || d == 6 || d == 9) good = true;
                x /= 10;
            }
            if (valid && good) res++;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun rotatedDigits(n: Int): Int {
        var res = 0
        for (i in 1..n) {
            var x = i
            var valid = true
            var good = false
            while (x > 0) {
                val d = x % 10
                if (d == 3 || d == 4 || d == 7) { valid = false; break }
                if (d == 2 || d == 5 || d == 6 || d == 9) good = true
                x /= 10
            }
            if (valid && good) res++
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def rotatedDigits(n):
    res = 0
    for i in range(1, n+1):
        x = i
        valid, good = True, False
        while x > 0:
            d = x % 10
            if d in (3,4,7):
                valid = False
                break
            if d in (2,5,6,9):
                good = True
            x //= 10
        if valid and good:
            res += 1
    return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

pub fn rotated_digits(n: i32) -> i32 {
    let mut res = 0;
    for i in 1..=n {
        let mut x = i;
        let mut valid = true;
        let mut good = false;
        while x > 0 {
            let d = x % 10;
            if d == 3 || d == 4 || d == 7 { valid = false; break; }
            if d == 2 || d == 5 || d == 6 || d == 9 { good = true; }
            x /= 10;
        }
        if valid && good { res += 1; }
    }
    res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function rotatedDigits(n: number): number {
    let res = 0;
    for (let i = 1; i <= n; ++i) {
        let x = i, valid = true, good = false;
        while (x > 0) {
            const d = x % 10;
            if (d === 3 || d === 4 || d === 7) { valid = false; break; }
            if (d === 2 || d === 5 || d === 6 || d === 9) good = true;
            x = Math.floor(x / 10);
        }
        if (valid && good) res++;
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n * D) (D = number of digits per number, at most 5)
  • 🧺 Space complexity: O(1)