Number of Strobogrammatic Number in Range [l, r] (Strobogrammatic Number III)
Given two strings l and r, which represent two integers l and r where l <= r. The task is to return the number of strobogrammatic numbers in the range [l, r]. A strobogrammatic number is a number that looks the same when rotated 180 degrees (i.e., when viewed upside down).
Example:
Input: l = “50”, r = “100”
Output: 3Input: l = “0”, r = “0”
Output: 1
Approach:
For any number string s, the strobogrammatic number can only be
8 + s[1:-1] + 8, 1 + s[1:-1] + 1, 0 + s[1:-1] + 0, 6 + s[1:-1] + 9, 9 + s[1:-1] + 6.
It’s easy to get that for any digit i, the number of the strobogrammatic string on that digit is dp[i] = dp[i – 2] * 5
As the constraint gives that the highest digit is 15, so at most we can get 3* (5 ** 7) = 234375 numbers with the given highest constraint, which is still possible to generate all of them.
Step-by-step algorithm:
- Use dp to generate all of the strobogrammatic strings,
- Convert them to number and add to a SortedSet()
- For this step, be careful the numbers strings that start with “0“,
- All of those should be removed except the real “0“
- Use binary search to find the left and right index with given l and r
Below is the implementation of the algorithm:
#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 = "50", r = "100";
cout << strobogrammaticInRange(l, r) << endl;
return 0;
}
import java.util.*;
public class Main {
public static int strobogrammaticInRange(String l,
String r)
{
// Create a map to store the strobogrammatic numbers
// of different lengths
Map<Integer, List<String> > dp = new HashMap<>();
dp.put(0, Arrays.asList(
"0", "1",
"8")); // Base case: strobogrammatic
// numbers of length 0
dp.put(1, Arrays.asList(
"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.length(); ++i) {
dp.put(i, new ArrayList<>());
for (String j : dp.get(i - 2)) {
// Append the strobogrammatic pairs to the
// beginning and end of the strobogrammatic
// number of length i - 2
dp.get(i).add("0" + j + "0");
dp.get(i).add("1" + j + "1");
dp.get(i).add("8" + j + "8");
dp.get(i).add("6" + j + "9");
dp.get(i).add("9" + j + "6");
}
}
// Convert the strobogrammatic strings to integers
// and store them in a sorted array
List<Integer> nums = new ArrayList<>();
for (Map.Entry<Integer, List<String> > entry :
dp.entrySet()) {
for (String v : entry.getValue()) {
// Ignore the strobogrammatic numbers that
// start with 0 and have more than one digit
if (v.charAt(0) == '0' && v.length() > 1)
continue;
nums.add(Integer.parseInt(v));
}
}
Collections.sort(nums);
// Find the indices of the l and r strings in the
// sorted array
int left = Collections.binarySearch(
nums, Integer.parseInt(l));
int right = Collections.binarySearch(
nums, Integer.parseInt(r));
// Handle the case when l and r are not exact
// matches in the sorted array
if (left < 0)
left = -left - 1;
if (right < 0)
right = -right - 1;
// Return the number of strobogrammatic numbers in
// the range [l, r]
return right - left;
}
public static void main(String[] args)
{
String l = "50", r = "100";
System.out.println(strobogrammaticInRange(l, r));
}
}
// This code is contributed by Shivam Gupta
from collections import defaultdict
from bisect import bisect_left, bisect_right
def strobogrammaticInRange(l, r):
# Create a dictionary to store the strobogrammatic numbers of
# different lengths
dp = defaultdict(list)
dp[0] = ["0", "1", "8"] # Base case: strobogrammatic numbers of length 0
# Base case: strobogrammatic numbers of length 1
dp[1] = ["00", "11", "88", "69", "96"]
# Generate strobogrammatic numbers of length i for i from 2 to the
# length of the r string
for i in range(2, len(r) + 1):
dp[i] = []
for j in dp[i - 2]:
# Append the strobogrammatic pairs to the beginning
# and end of the strobogrammatic number of length i - 2
dp[i].append("0" + j + "0")
dp[i].append("1" + j + "1")
dp[i].append("8" + j + "8")
dp[i].append("6" + j + "9")
dp[i].append("9" + j + "6")
# Convert the strobogrammatic strings to integers and store them in
# a sorted array
nums = []
for length in dp:
for v in dp[length]:
# Ignore the strobogrammatic numbers that start with 0 and
# have more than one digit
if v[0] == '0' and len(v) > 1:
continue
nums.append(int(v))
nums.sort()
# Find the indices of the l and r strings in the sorted array
left = bisect_left(nums, int(l))
right = bisect_right(nums, int(r))
# Return the number of strobogrammatic numbers in the range [l, r]
return right - left
if __name__ == "__main__":
l = "50"
r = "100"
print(strobogrammaticInRange(l, r))
# This code is contributed by Ayush Mishra
Output
3
Time complexity: O(n log n), where n is the length of the r string. This is because the code generates all strobogrammatic numbers of lengths from 0 to n, which takes O(n) time, and then sorts these numbers, which takes O(n log n) time.
Auxiliary space: O(n). This is because the code uses a map to store the strobogrammatic numbers of different lengths, and the total number of these numbers is proportional to the length of the r string.