Rotated Digits

medium math digits enumeration

Problem

A good number, when each digit is rotated 180 degrees, becomes a different valid number. Digits 0,1,8 stay the same, 2/5 and 6/9 swap, and 3/4/7 are invalid. Count integers in [1, n] that are good.

Inputn = 10

Output4

2, 5, 6, 9 are good numbers in [1, 10].

def rotatedDigits(n):
    count = 0
    for i in range(1, n + 1):
        s = str(i)
        if any(c in '347' for c in s):
            continue
        if any(c in '2569' for c in s):
            count += 1
    return count

var rotatedDigits = function(n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        const s = String(i);
        if (/[347]/.test(s)) continue;
        if (/[2569]/.test(s)) count++;
    }
    return count;
};

class Solution {
    public int rotatedDigits(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            String s = Integer.toString(i);
            if (s.matches(".*[347].*")) continue;
            if (s.matches(".*[2569].*")) count++;
        }
        return count;
    }
}

class Solution {
public:
    int rotatedDigits(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            string s = to_string(i);
            if (s.find_first_of("347") != string::npos) continue;
            if (s.find_first_of("2569") != string::npos) count++;
        }
        return count;
    }
};

Explanation

A number is "good" when rotating each digit 180° gives a valid but different number. We can decide this by just looking at which digits it contains — no actual rotation needed.

The digits fall into three groups: 3, 4, 7 become invalid when flipped; 0, 1, 8 stay exactly the same; and 2, 5, 6, 9 turn into a different digit.

So a number is good if it has no 3/4/7 (otherwise the rotation is invalid) AND has at least one of 2/5/6/9 (otherwise it would rotate to itself and not be "different"). The loop checks both conditions on each i from 1 to n and counts the good ones.

Example: in [1, 10], the good numbers are 2, 5, 6, 9. Numbers like 1 or 8 rotate to themselves (not different), and there's no 3/4/7 issue here — so the count is 4.

This works because the validity of a multi-digit number depends only on each digit independently, so a quick character scan settles it.

Time: O(n log n) Space: O(log n)