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

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 104


class Solution:
    def rotatedDigits(self, n: int) -> int:
        d={
            0:0,
            1:1,
            2:5,
            3:None,
            4: None,
            5:2,
            6:9,
            7:None,
            8:8,
            9:6
        }
        res=0
        for i in range(n+1):
            t=i
            pos=0
            temp=0
            status=True
            while t>0:
                r=d[t%10] #Every Digit Rotation Is Must, We Don't Have Choice To Leave It Without Rotating
                if r is None:
                    status=False
                    break

                temp+=((10**pos)*r)
                pos+=1
                t=t//10

            if temp!=i and status:
                res+=1
        return res
class Solution {
    public int rotatedDigits(int n) {
        int ans=0;
        for(int i=1; i<=n; i++){
            int k = i;
            boolean bool1=true; boolean bool2=false;
            while(k>0){
                int m=k%10;
                if(m==3 || m==4 || m==7){ bool1=false; break; }
                else if(m==2 || m==5 || m==6 || m==9){ bool2=true; }
                k/=10;
            }
            if(bool1 && bool2){ ans++; }
        }
        return ans;
    }
}
class Solution
{
public:
    bool isValid(int n)
    {
        bool check = false;
        while (n > 0)
        {
            int k = n % 10;
            if (k == 2 || k == 5 || k == 6 || k == 9)
                check = true;
            if (k == 3 || k == 4 || k == 7)
                return false;
            n /= 10;
        }
        return check;
    }
    int rotatedDigits(int n)
    {
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; i++)
        {
            if (isValid(i))
                dp[i]++;
            dp[i] += dp[i - 1];
        }
        return dp[n];
    }
};
/**
 * @param {number} n
 * @return {number}
 */
var rotatedDigits = function(n) {
    let count=0;
    for(let i=1;i<=n;i++){
        let str=i.toString().split("");
        let f=str.filter(s=> s!=1 && s!=0 && s!=8);
        if(f.length===0) continue;
        let g=f.filter(s=> s!=5 && s!=2 && s!=6 && s!=9);
        if(g.length===0) count++;
    }
    return count;
};
Rotated Digits