1
class Solution {
2
 public:
3
  bool isValid(int n) {
4
    bool check = false;
5
    while (n > 0) {
6
      int k = n % 10;
7
      if (k == 2 || k == 5 || k == 6 || k == 9) check = true;
8
      if (k == 3 || k == 4 || k == 7) return false;
9
      n /= 10;
10
    }
11
    return check;
12
  }
13
  int rotatedDigits(int n) {
14
    vector<int> dp(n + 1, 0);
15
    for (int i = 2; i <= n; i++) {
16
      if (isValid(i)) dp[i]++;
17
      dp[i] += dp[i - 1];
18
    }
19
    return dp[n];
20
  }
21
};