Submission

Score: 10

User: lazy

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.020 second

Submitted On: 2025-10-14 23:35:40

#include <bits/stdc++.h>
using namespace std;


/*

case l is even

2 digits : 00, 11, 69 , 88
4 digits : case base 00
            0000, 1001, 6009, 8008
           case base 11
            0110, 1111, 6119, 8118
            ...
there is noticable recurrence/branching

case l is odd
1 digits : 1, 8, 0
3 digits : case base 1
            010 , 111 , 619 , 818

        ...
same idea but different base cases.


we will use 2d array

dp[i][j] where i stores amount of digit, j will store all possible numbers in the digit (size will not be constant)

when we call 5 > 3 > 1;
when we call 4 > 2;



*/



vector<vector<string>> dp(100);
map<string,string> pairs = {
    {"0","0"},
    {"1","1"},
    {"6","9"},
    {"8","8"},
    {"9","6"},

};

vector<string> at_i_digit(int i) {




    if (i == 1) {
        return {"0","1","8"};
    }

    if (i == 2) {
        return {"0","11","69","88"};
    }

    if (dp[i].size() == 0) {
        vector<string> result;
        vector<string> previous = at_i_digit(i-2);
        for (int x = 0; x < previous.size(); x++) {
            for (const auto& pair : pairs) {
                result.push_back(pair.first + previous[x] + pair.second);
            }
        }

        dp[i] = result;
    }


    return dp[i];


}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> ans = at_i_digit(5);

    long long lower, upper;
    int count = 0;

    cin >> lower >> upper;

    int ndigits_l = to_string(lower).length();
    int ndigits_u = to_string(upper).length();

    for (int n = ndigits_l; n <= ndigits_u; n++) {
        vector<string> result = at_i_digit(n);

        for (int i = 0 ; i < result.size(); i++) {
            int n = stoi(result[i]);
            if (lower <= n && n <= upper ) {
                count++;
            }
        }
    }

    cout << count;

    return 0;
}