Leetcode 804 Solution

class Solution {
public:
    int _rotateDigits(const vector<int>& digits, int i, bool high, bool same) {
        if (i == digits.size())
            return same ? 0 : 1;

        int digit = digits[i];
        int res = 0;
        int limit = high ? digit : 9;

        for (int j = 0; j <= limit; j++)
        {
            if (j == 0 || j == 1 || j == 8)
                res += _rotateDigits(digits, i + 1, j == limit && high, same);
            else if (j == 2 || j == 5 || j == 6 || j == 9)
                res += _rotateDigits(digits, i + 1, j == limit && high, false);
        }

        return res;
    }

    int rotatedDigits(int N) {
        vector<int> digits;

        while (N)
        {
            digits.push_back(N % 10);
            N /= 10;
        }

        reverse(digits.begin(), digits.end());

        return _rotateDigits(digits, 0, true, true);
    }
};