Rotated Digits Solutions in C++

/// Source : https://leetcode.com/problems/rotated-digits/description/
/// Author : liuyubobobo
/// Time   : 2018-02-24

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Brute Force
/// Time Complexity: O(NlogN)
/// Space Complexity: O(logN)
class Solution {

public:
    int rotatedDigits(int N) {

        int res = 0;
        for(int i = 1 ; i <= N ; i ++){
            vector<int> digits = get_digits(i);
            bool ok = true;
            for(int d: digits)
                if(d == 3 || d == 4 || d ==7){
                    ok = false;
                    break;
                }

            if(ok){
                rotate(digits);
                int num = get_num(digits);
                if(num != i)
                    res ++;
            }
        }
        return res;
    }

private:
    int get_num(const vector<int>& digits){
        int x = 0;
        for(int d: digits)
            x = x * 10 + d;
        return x;
    }
    void rotate(vector<int>& digits){

        for(int i = 0 ; i < digits.size() ; i ++)
            if(digits[i] == 2)
                digits[i] = 5;
            else if(digits[i] == 5)
                digits[i] = 2;
            else if(digits[i] == 6)
                digits[i] = 9;
            else if(digits[i] == 9)
                digits[i] = 6;
            else
                assert(digits[i] == 0 || digits[i] == 1 || digits[i] == 8);
    }

    vector<int> get_digits(int x){

        vector<int> res;
        while(x){
            res.push_back(x%10);
            x /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

int main() {

    cout << Solution().rotatedDigits(10) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/rotated-digits/description/
/// Author : liuyubobobo
/// Time   : 2018-03-05

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Brute Force
/// Using String
///
/// Time Complexity: O(NlogN)
/// Space Complexity: O(logN)
class Solution {

public:
    int rotatedDigits(int N) {

        int res = 0;
        for(int i = 1 ; i <= N ; i ++){
            string digits = to_string(i);
            string rdigits = digits;
            if(ok(digits, rdigits))
                res ++;
        }
        return res;
    }

private:
    bool ok(const string& digits, string& rdigits){
        for(int i = 0 ; i < rdigits.size() ; i ++)
            if(rdigits[i] == '3' || rdigits[i] == '4' || rdigits[i] == '7')
                return false;
            else if(rdigits[i] == '2')
                rdigits[i] = '5';
            else if(rdigits[i] == '5')
                rdigits[i] = '2';
            else if(rdigits[i] == '6')
                rdigits[i] = '9';
            else if(rdigits[i] == '9')
                rdigits[i] = '6';
        return digits != rdigits;
    }

};

int main() {

    cout << Solution().rotatedDigits(10) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/rotated-digits/description/
/// Author : liuyubobobo
/// Time   : 2018-03-05

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Brute Force
/// We need to write using only digits from 0125689,
/// and write at least one digit from 2569.
///
/// Time Complexity: O(NlogN)
/// Space Complexity: O(logN)
class Solution {

public:
    int rotatedDigits(int N) {

        int res = 0;
        for(int i = 1 ; i <= N ; i ++)
            if(ok(i, false))
                res ++;
        return res;
    }

private:
    bool ok(int num, bool flag){
        if(num == 0)
            return flag;

        int d = num % 10;
        if(d == 3 || d == 4 || d == 7)
            return false;

        if(d == 0 || d == 1 || d == 8)
            return ok(num / 10, flag);

        return ok(num / 10, true);
    }

};

int main() {

    cout << Solution().rotatedDigits(10) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/rotated-digits/description/
/// Author : liuyubobobo
/// Time   : 2018-03-05

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Memory Search
///
/// We need to write using only digits from 0125689,
/// and write at least one digit from 2569.
///
/// dp[i][eq][contain2569] means we search first i digits,
/// and the i-th digit is equal (or not) to the i-th digit in N
/// and the search has (or not) already meet a digit of 2569
///
/// Time Complexity: O(logN)
/// Space Complexity: O(logN)
class Solution {

private:
    vector<vector<vector<int>>> memo;

public:
    int rotatedDigits(int N) {

        string N_str = to_string(N);
        memo = vector<vector<vector<int>>>(N_str.size(), vector<vector<int>>(2, vector<int>(2, -1)));
        return search(0, true, false, N_str);
    }

private:
    int search(int index,bool eq, bool contain2569, const string& s){

        if(index == s.size())
            return contain2569 ? 1 : 0;

        if(memo[index][eq][contain2569] != -1)
            return memo[index][eq][contain2569];

        int res = 0;
        char bound = eq ? s[index] : '9';
        for(char c = '0' ; c <= bound ; c ++){
            if(c == '3' || c == '4' || c == '7')
                continue;

            bool is2569 = (c == '2' || c == '5' || c == '6' || c =='9');
            if(!eq)
                res += search(index + 1, eq, contain2569 || is2569, s);
            else if(c < bound)
                res += search(index + 1, false, contain2569 || is2569, s);
            else
                res += search(index + 1, true, contain2569 || is2569, s);
        }

        return memo[index][eq][contain2569] = res;
    }

};

int main() {

    cout << Solution().rotatedDigits(10) << endl; // 4
    cout << Solution().rotatedDigits(857) << endl; // 247
    return 0;
}

/// Source : https://leetcode.com/problems/rotated-digits/description/
/// Author : liuyubobobo
/// Time   : 2018-03-05

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Dynamic Programming
///
/// We need to write using only digits from 0125689,
/// and write at least one digit from 2569.
///
/// dp[i][eq][contain2569] means we search first i digits,
/// and the i-th digit is equal (or not) to the i-th digit in N
/// and the search has (or not) already meet a digit of 2569
///
/// Time Complexity: O(logN)
/// Space Complexity: O(logN)
class Solution {

public:
    int rotatedDigits(int N) {

        string N_str = to_string(N);
        vector<vector<vector<int>>> memo(N_str.size() + 1, vector<vector<int>>(2, vector<int>(2, 0)));

        memo[N_str.size()][false][true] = 1;
        memo[N_str.size()][true][true] = 1;
        for(int index = N_str.size() - 1 ; index >= 0 ; index --)
            for(int eq = 0 ; eq <= 1 ; eq ++)
                for(int contain2569 = 0 ; contain2569 <= 1 ; contain2569 ++){

                    int res = 0;
                    char bound = eq ? N_str[index] : '9';
                    for(char c = '0' ; c <= bound ; c ++){
                        if(c == '3' || c == '4' || c == '7')
                            continue;

                        bool is2569 = (c == '2' || c == '5' || c == '6' || c =='9');
                        if(!eq)
                            res += memo[index+1][eq][contain2569 || is2569];
                        else if(c < bound)
                            res += memo[index+1][false][contain2569 || is2569];
                        else
                            res += memo[index+1][true][contain2569 || is2569];
                    }
                    memo[index][eq][contain2569] = res;
                }

        return memo[0][true][false];
    }

};

int main() {

    cout << Solution().rotatedDigits(10) << endl; // 4
    cout << Solution().rotatedDigits(857) << endl; // 247
    return 0;
}