788. Rotated Digits

Problem statement

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].

Examples

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

1 <= n <= 10^4

Explanation

Since n <= 10^4, a bruteforce solution would be enough to pass for these constraints. For each number from 1 to n, check if it contains only the valid digits. If yes, then the number would add to our answer.

But what if n <= 10^15?

We can’t write a bruteforce code to pass for such large constraints.

First, we generate all the numbers with the valid digits and which are <= n. But since there is a restriction to not count numbers which are the same as before after rotating the digits by 180, we must avoid counting them.

To achieve this, we can generate all possible numbers which can be formed using just 0, 1, 8 and remove them from our answer, since their mirror version will be the same as the original and hence the number would remain unchanged. This can be efficiently computed using a Digit DP approach.

Code

Bruteforce Code

class Solution {
public:
    int rotatedDigits(int n) {
        int ans = 0;
        unordered_map<char, char> mp = {
            {'0', '0'}, {'1', '1'}, {'8', '8'},
            {'2', '5'}, {'5', '2'},
            {'6', '9'}, {'9', '6'}
        };        
        for(int i=1;i<=n;i++){
            auto s = to_string(i);
            bool ok = 1;
            for(auto &j:s) if(mp.find(j)==mp.end()) ok = 0;
            if(ok==0) continue;
            for(auto &j:s) j = mp[j];
            ans += (stoll(s)!=i);
        }
        return ans;
    }
};

Optimal Digit DP Code

#define ll long long
class Solution {
public:
    int rotatedDigits(int n) {
        set<int> A = {'0','1','8'}, B = {'0','1','2','5','6','8','9'};
        int dp[6][2][2];
        memset(dp,-1,sizeof dp);
        auto solve = [&](auto &&solve,int i,auto &s, auto &st, int leading,int tight)->ll{
            if(i == s.size()){
                return (leading==0);
            }
            if(dp[i][leading][tight]!=-1) return dp[i][leading][tight];
            ll ans = 0;
            auto ub = (tight ? s[i] : '9');
            for(auto c = '0'; c <= ub; c++){
                if(st.find(c)==st.end()) continue;
                ans += solve(solve,i+1,s,st,leading && (c=='0'), tight && c==ub);
            }
            return dp[i][leading][tight] = ans;
        };
        auto s = to_string(n);
        ll R = solve(solve,0,s,B,1,1);
        memset(dp,-1,sizeof dp);
        ll L = solve(solve,0,s,A,1,1);
        return R-L;
    }
};