Submission

Score: 20

User: nate213121

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.002 second

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

#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, long long iteration)
{
    long long iCurr = stoll(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], iteration + 1);
        }
    }
}

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

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