Submission

PPxxxxxxxx

Score: 20

User: meme_boi2

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.116 second

Submitted On: 2024-12-04 14:56:28

//I steak this code from google
#include <bits/stdc++.h>
using namespace std;

int strobogrammaticInRange(string l, string r)
{
    // Create a map to store the strobogrammatic numbers of
    // different lengths
    unordered_map<int, vector<string> > dp;
    dp[0] = {
        "0", "1", "8"
    }; // Base case: strobogrammatic numbers of length 0
    dp[1] = {
        "00", "11", "88", "69", "96"
    }; // Base case: strobogrammatic numbers of length 1

    // Generate strobogrammatic numbers of length i for i
    // from 2 to the length of the r string
    for (int i = 2; i <= r.size(); ++i) {
        dp[i] = {};
        for (string j : dp[i - 2]) {
            // Append the strobogrammatic pairs to the
            // beginning and end of the strobogrammatic
            // number of length i - 2
            dp[i].push_back("0" + j + "0");
            dp[i].push_back("1" + j + "1");
            dp[i].push_back("8" + j + "8");
            dp[i].push_back("6" + j + "9");
            dp[i].push_back("9" + j + "6");
        }
    }

    // Convert the strobogrammatic strings to integers and
    // store them in a sorted array
    vector<int> nums;
    for (auto d : dp) {
        for (string v : d.second) {
            // Ignore the strobogrammatic numbers that start
            // with 0 and have more than one digit
            if (v[0] == '0' && v.size() > 1)
                continue;
            nums.push_back(stoi(v));
        }
    }
    sort(nums.begin(), nums.end());

    // Find the indices of the l and r strings in the
    // sorted array
    auto left
        = lower_bound(nums.begin(), nums.end(), stoi(l));
    auto right
        = upper_bound(nums.begin(), nums.end(), stoi(r));

    // Return the number of strobogrammatic numbers in the
    // range [l, r]
    return distance(left, right);
}

int main()
{

    string l, r;
    cin >> l >> r;
    cout << strobogrammaticInRange(l, r) << endl;
    return 0;
}