Submission

Score: 20

User: nate213121

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.045 second

Submitted On: 2026-09-13 20:32:13

#include <bits/stdc++.h>

using namespace std;

long long low, high;
long long highLength;

long long c = 0;
vector<string> usableNumbers = {"0", "1", "8", "6", "9"};
map<string, string> pairedWith;

void generatePalindromes(string curr)
{
    if(curr != "")
    {
        long long iCurr = stoll(curr);
        if(to_string(iCurr) == curr)
        {
            if(iCurr >= low && iCurr <= high)
            {
                //cout << curr << endl;
                c++;
            }
        }
    }
    if(curr.size() > highLength)
    {
        return;
    }
    for(auto& u:usableNumbers)
    {
        if(u != "0")
        {
            generatePalindromes(u + curr + pairedWith[u]);
        }
    }
}

int main()
{
    pairedWith["0"] = "0";
    pairedWith["1"] = "1";
    pairedWith["8"] = "8";
    pairedWith["6"] = "9";
    pairedWith["9"] = "6";
    cin >> low >> high;
    highLength = to_string(high).size();

    for(auto& s:usableNumbers)
    {
        if(s != "6" && s != "9")
        {
            generatePalindromes(s);
        }
    }
    generatePalindromes("");
    cout << c;
    return 0;
}