248. Strobogrammatic Number III

HardRecursionArrayString
Leetcode Link

Problem Description

The challenge presented involves identifying a special class of numbers known as "strobogrammatic numbers." A strobogrammatic number is one that retains its original value when rotated by 180 degrees. Imagine flipping the number upside down; if it still reads the same, it's strobogrammatic. For example, 69 and 88 are strobogrammatic, while 70 is not.

Given two string inputs, low and high, which represent the lower and upper bounds of a numeric range, the task is to calculate the total count of strobogrammatic numbers that fall within this range, including the bounds themselves. We need to ensure that we convert low and high from strings to integers because we are working with numeric comparisons.

This is a problem that combines counting, string manipulation, and number theory. Solvers must understand the nature of strobogrammatic numbers and devise a strategy to generate and count all valid strobogrammatic numbers within the specified interval.

Intuition

To approach this solution, we need to generate strobogrammatic numbers in an efficient way, which requires careful consideration given the potentially large range. The direct approach of checking each number within the range will be inefficient, especially for large bounds.

Here are the critical steps to the algorithm:

  1. We observe that strobogrammatic numbers are symmetrical and recursively build them from the middle outwards.
  2. For a given length u, we can construct strobogrammatic numbers by placing pairs of strobogrammatic digits at the start and end of an already-formed strobogrammatic number of length u - 2. This uses a depth-first search (DFS) approach.
  3. The valid pairs to form strobogrammatic numbers are ('0', '0'), ('1', '1'), ('8', '8'), ('6', '9'), and ('9', '6').
  4. We include '0' at the ends only if we are not at the outermost layer, since a number cannot start with '0'.
  5. We execute this DFS approach in a loop starting from the length of the low string to the length of the high string, building all possible strobogrammatic numbers of each length.
  6. We check if each generated strobogrammatic number falls within the low to high range after converting it to an integer.
  7. Increment a counter each time we find a valid strobogrammatic number within the range.

This approach focuses on generating only potentially valid strobogrammatic numbers rather than searching through the entire range, thus reducing the number of necessary checks and improving efficiency.

Learn more about Recursion patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The provided solution involves the use of recursion to generate strobogrammatic numbers with a depth-first search (DFS) approach. To do so, a helper function called dfs is used to construct these numbers.

Here's a detailed explanation of how the solution operates:

  • The dfs function is defined to construct strobogrammatic numbers of a given length u. It has two base cases:

    • If u == 0, the function returns an empty list containing just an empty string [''], since there are no digits in a zero-length number.
    • If u == 1, the function returns a list of single-digit strobogrammatic numbers ['0', '1', '8'].

  • For other cases, dfs is called recursively on u - 2 to return the list of strobogrammatic numbers that are two digits shorter. We can sandwich pairs of strobogrammatic digits around each returned number to form new strobogrammatic numbers of length u.

  • These digit pairs are added only if the resulting number is not longer than the maximum length (n) being checked. The pairs used are ('1', '1'), ('8', '8'), ('6', '9'), and ('9', '6'). If the length is not the full target length n, we can also use the pair ('0', '0'), but leading zeros are not added to full-length numbers.

  • After defining the dfs function, the lengths a and b represent the lengths of the low and high strings, respectively, which are used to get the length range of strobogrammatic numbers.

  • The main part of the solution iterates over each length from a to b, inclusive, generating strobogrammatic numbers of that length using the dfs function.

  • The generated strings are checked to determine if they fall within the specified numeric range [low, high]. This is done by converting the strobogrammatic string to an integer and comparing it against the numeric low and high. If it falls within the range, the counter ans is incremented.

  • Finally, the ans value containing the count of strobogrammatic numbers in the specified range is returned.

Throughout the implementation, key algorithmic patterns such as recursion, DFS, and generating combinatorial output based on constraints are used to build an efficient solution for counting strobogrammatic numbers within a given range.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's consider a small example where the low string is "10" and the high string is "100". We need to find out how many strobogrammatic numbers exist between 10 and 100.

Using the solution approach, we would start by finding strobogrammatic numbers of different lengths within the inclusive range of the lengths of "10" (length 2) and "100" (length 3).

We iterate through lengths 2 and 3 since no strobogrammatic number of length 1 falls between 10 and 100.

For length 2 (same as the length of "10"), the possible strobogrammatic numbers are:

  • 11, which is not strobogrammatic because it doesn't retain its value when flipped.
  • 69, which is strobogrammatic.
  • 88, which is strobogrammatic.
  • 96, which is strobogrammatic.
  • 00 is excluded as it's not a valid two-digit number because numbers cannot start with '0'.

Out of these, only 69, 88, and 96 are valid and fall within the given range (10 to 100).

Next, for length 3 (same as the length of "100"), the possible strobogrammatic numbers would need to have a form such as "x0x", "x1x", or "x8x" (the middle digit can be '0', '1', or '8'). But we quickly realize that none of these forms can create a valid strobogrammatic number due to the nature of the digit '0' in the middle. As a result, there are no valid 3-digit strobogrammatic numbers between 10 and 100.

As such, the total count of strobogrammatic numbers between 10 and 100 is 3.

In this case, the dfs function would have worked by first generating numbers of length 2 by sandwiching the central parts [''] with all valid pairs except ('0', '0') and then generating numbers of length 3 by sandwiching the central parts ['0', '1', '8'] with valid pairs. However, since all 3-digit combinations fall outside the range, they would not be counted.

The final answer would therefore be 3, representing the strobogrammatic numbers 69, 88, and 96.

Solution Implementation

1class Solution:
2    def strobogrammaticInRange(self, low: str, high: str) -> int:
3        # Helper function to generate strobogrammatic numbers of length 'length'
4        def generate_strobogrammatic(length):
5            # Base case for a strobogrammatic number of length 0 is an empty string
6            if length == 0:
7                return ['']
8            # Base case for length 1 (single digit strobogrammatic numbers)
9            if length == 1:
10                return ['0', '1', '8']
11            sub_ans = []
12            # Recursive call to get the inner strobogrammatic number
13            for sub_number in generate_strobogrammatic(length - 2):
14                # Adding the strobogrammatic pairs to the sub_number
15                for pair in ('11', '88', '69', '96'):
16                    sub_ans.append(pair[0] + sub_number + pair[1])
17                # Numbers like '060', '080' etc. cannot be at the beginning or end
18                # So we add them only when we're not at the outermost level
19                if length != num_length:
20                    sub_ans.append('0' + sub_number + '0')
21            return sub_ans
22
23        min_length, max_length = len(low), len(high)
24        low, high = int(low), int(high)
25        count = 0  # Counter for strobogrammatic numbers within the range
26
27        # Loop through all lengths from min_length to max_length
28        for num_length in range(min_length, max_length + 1):
29            # generate strobogrammatic numbers of length 'num_length'
30            for num_str in generate_strobogrammatic(num_length):
31                # Convert the string to an integer and check if it's within range
32                if low <= int(num_str) <= high:
33                    count += 1
34        return count  # Return the count of strobogrammatic numbers within the range
35
1class Solution {
2    // Pairs of strobogrammatic numbers that are each other's reflection.
3    private static final int[][] STROBO_PAIRS = {{1, 1}, {8, 8}, {6, 9}, {9, 6}};
4    private int targetLength;
5
6    // Public method to count the strobogrammatic numbers in a given range.
7    public int strobogrammaticInRange(String low, String high) {
8        int minLength = low.length(), maxLength = high.length();
9        long lowerBound = Long.parseLong(low), upperBound = Long.parseLong(high);
10        int count = 0;
11
12        // Loop through each length from low to high
13        for (targetLength = minLength; targetLength <= maxLength; ++targetLength) {
14            // Generate all strobogrammatic numbers of the current length.
15            for (String num : generateStrobogrammaticNumbers(targetLength)) {
16                long value = Long.parseLong(num);
17                // Check if the generated number is within the range, if so, increment the count.
18                if (lowerBound <= value && value <= upperBound) {
19                    ++count;
20                }
21            }
22        }
23        return count;
24    }
25
26    // Helper method to generate strobogrammatic numbers of a given length.
27    private List<String> generateStrobogrammaticNumbers(int length) {
28        // Base case for recursion: if length is 0, return a list with an empty string.
29        if (length == 0) {
30            return Collections.singletonList("");
31        }
32        // If the length is 1, we can use '0', '1', and '8' as they look same even after rotation.
33        if (length == 1) {
34            return Arrays.asList("0", "1", "8");
35        }
36        List<String> result = new ArrayList<>();
37        // Get all the strobogrammatic numbers of length minus two.
38        for (String middle : generateStrobogrammaticNumbers(length - 2)) {
39            // Surround the middle part with each pair of STROBO_PAIRS.
40            for (int[] pair : STROBO_PAIRS) {
41                result.add(pair[0] + middle + pair[1]);
42            }
43            // If this is not the outermost layer, we can add '0' at both ends as well.
44            if (length != targetLength) {
45                result.add("0" + middle + "0");
46            }
47        }
48        return result;
49    }
50}
51
1#include <vector>
2#include <string>
3#include <functional> // For std::function
4#include <utility> // For std::pair
5
6using std::vector;
7using std::string;
8using std::function;
9using std::pair;
10using std::stoll; // For converting string to long long
11
12using ll = long long; // Define 'll' as an alias for 'long long'
13
14class Solution {
15public:
16    // Define pairs that are strobogrammatic (they look the same when rotated 180 degrees)
17    const vector<pair<char, char>> strobogrammaticPairs = {{'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
18
19    int strobogrammaticInRange(string low, string high) {
20      
21        // Declare the current size of strobogrammatic numbers to generate
22        int currentSize;
23
24        // Depth-First Search function to generate strobogrammatic numbers of a certain size
25        function<vector<string>(int)> generateStrobogrammatic = [&](int size) {
26            // Base cases
27            if (size == 0) return vector<string>{""};
28            if (size == 1) return vector<string>{"0", "1", "8"};
29          
30            vector<string> results;
31            // Generate smaller strobogrammatic numbers and append new pairs to them
32            for (auto& smallerStr : generateStrobogrammatic(size - 2)) {
33                for (auto& [left, right] : strobogrammaticPairs) {
34                    results.push_back(left + smallerStr + right);
35                }
36                // If not at the outermost layer, we can add '0' at both ends
37                if (size != currentSize) {
38                    results.push_back('0' + smallerStr + '0');
39                }
40            }
41            return results;
42        };
43
44        // Get sizes of the provided range
45        int sizeLow = low.size(), sizeHigh = high.size();
46      
47        // Initialize counter for valid strobogrammatic numbers within the range
48        int count = 0;
49      
50        // Convert string bounds to long long for numerical comparison
51        ll lowerBound = stoll(low), upperBound = stoll(high);
52      
53        // Generate strobogrammatic numbers for sizes within the inclusive range [sizeLow, sizeHigh]
54        for (currentSize = sizeLow; currentSize <= sizeHigh; ++currentSize) {
55          
56            // Generate strobogrammatic numbers of current size
57            for (auto& strobogrammaticNum : generateStrobogrammatic(currentSize)) {
58              
59                // Convert the strobogrammatic string to a number
60                ll value = stoll(strobogrammaticNum);
61              
62                // Check if the number is within the given range
63                if (lowerBound <= value && value <= upperBound) {
64                    ++count;
65                }
66            }
67        }
68        // Return the total count of strobogrammatic numbers in the range
69        return count;
70    }
71};
72
1// Use the 'bigint' type to handle large integer values in TypeScript
2type ll = bigint;
3
4// Define pairs that are strobogrammatic (they look the same when rotated 180 degrees)
5const strobogrammaticPairs: Array<[string, string]> = [['1', '1'], ['8', '8'], ['6', '9'], ['9', '6']];
6
7// Depth-First Search function to generate strobogrammatic numbers of a certain size
8const generateStrobogrammatic = (size: number, maxSize: number): string[] => {
9    // Base cases: return arrays of empty string or single strobogrammatic digits
10    if (size === 0) return [''];
11    if (size === 1) return ['0', '1', '8'];
12  
13    let results: string[] = [];
14
15    // Generate smaller strobogrammatic numbers and append new pairs to them
16    const smallerNumbers = generateStrobogrammatic(size - 2, maxSize);
17    for (const smallerStr of smallerNumbers) {
18        for (const [left, right] of strobogrammaticPairs) {
19            results.push(`${left}${smallerStr}${right}`);
20        }
21        // If not at the outermost layer, we can add '0' at both ends
22        if (size !== maxSize) {
23            results.push(`0${smallerStr}0`);
24        }
25    }
26    return results;
27};
28
29// Function that calculates the count of strobogrammatic numbers within a given range
30const strobogrammaticInRange = (low: string, high: string): number => {
31    // Initialize counter for valid strobogrammatic numbers within the range
32    let count: number = 0;
33  
34    // Get sizes of the provided range
35    const sizeLow: number = low.length;
36    const sizeHigh: number = high.length;
37  
38    // Convert string bounds to 'bigint' for numerical comparison
39    const lowerBound: ll = BigInt(low);
40    const upperBound: ll = BigInt(high);
41  
42    // Generate strobogrammatic numbers for sizes within the inclusive range [sizeLow, sizeHigh]
43    for (let currentSize: number = sizeLow; currentSize <= sizeHigh; ++currentSize) {
44      
45        // Generate strobogrammatic numbers of the current size
46        const strobogrammaticNumbers = generateStrobogrammatic(currentSize, currentSize);
47        for (const numStr of strobogrammaticNumbers) {
48            // Convert the strobogrammatic string to a number
49            const value: ll = BigInt(numStr);
50          
51            // Check if the number is within the given range
52            if (lowerBound <= value && value <= upperBound) {
53                count++;
54            }
55        }
56    }
57  
58    // Return the total count of strobogrammatic numbers in the range
59    return count;
60};
61
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

The given code defines a Solution class with a method strobogrammaticInRange to find strobogrammatic numbers within a given range. A strobogrammatic number is a number that looks the same when rotated 180 degrees (e.g., 69, 88, 818).

Time Complexity

The time complexity of the solution can be analyzed as follows:

  • The recursive function dfs(u) generates all strobogrammatic numbers of length u.
  • For u=0 and u=1, it returns a fixed set of values, so this is constant time, O(1).
  • For u > 1, it recursively calls dfs(u - 2) and then iterates over the result, which we'll call k, prepending and appending pairs of strobogrammatic digits to each string. Since there are four pairs it can append (except for the first and last digits, for which there's an additional pair), the number of operations for each recursive call relates to 4 * k + k (when u is not equal to n, considering zero-padded numbers), where k is the number of results from dfs(u - 2).
  • The number of strobogrammatic numbers of length u grows exponentially since every pair of digits can lead to 5 possibilities (including the '00' pair except at the top level). Therefore, approximately, the recursion's time complexity can be described by T(u) = 5 * T(u - 2) for u > 1, which indicates exponential growth.
  • The full search for generating strobogrammatic numbers ranges from length a (len(low)) to length b (len(high)), and the generation complexity would roughly be O(1) + O(5^((a-1)/2)) + ... + O(5^((b-1)/2)), which is dominated by the largest term O(5^((b-1)/2)) when b is even or O(5^(b/2)) when b is odd.

Considering the final for-loop that iterates over n from a to b inclusive and checks against the range, the overall time complexity would be approximated by O(b * 5^(b/2)), where b is the length of high.

Space Complexity

The space complexity can be analyzed as follows:

  • The recursion dfs(u) will have a maximum stack depth equivalent to b/2 (since each recursive step reduces u by 2).
  • Additionally, the space to store ans increases exponentially with the recursion, similar to time complexity, since every level of recursion generates a list of numbers that grows exponentially.
  • The space is freed once each recursive call completes, but the maximum held at any time relates to the maximum depth of the recursion tree, meaning the space complexity is also dominated by the output size of the deepest recursion call.

Given the above, the space complexity is also O(5^(b/2)), where b is the length of high.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫