788. Rotated Digits


Problem Description

The problem states that an integer x is considered good if it can be turned into a valid number by rotating each digit by 180 degrees. The rotation should transform the number into a different one, meaning we can't just leave any digit unchanged.

A digit is valid after rotation if it's still a number. There are specific digits that transform into themselves or others:

  • 0, 1, and 8 rotate to themselves.
  • 2 and 5 can rotate to each other.
  • 6 and 9 also rotate to each other.

Digits that are not in the above list become invalid after rotation.

Our task is to find the total number of good integers within the range from 1 up to and including n.

Intuition

To solve this problem, we approach it through recursive depth-first search (DFS) with caching (memoization) to improve performance. The idea is to iterate through each digit position, determining whether placing a certain digit there would contribute to the count of good numbers.

We define a recursive function dfs that considers the following arguments:

  • pos: current position in the number we're inspecting.
  • ok: a boolean indicating whether we've already placed a digit that becomes different after rotation (making the current number formation a good number).
  • limit: a boolean that tells us if we are limited by the original number n in choosing our digits.

The base case of the recursion is when pos <= 0, which means we've checked all the digit positions. If ok is True at this point, we've formed a good number, and we can increment our count.

During each recursive call, we try placing each digit (0-9) in the current position and make further recursive calls to fill the remaining positions. There are conditions though:

  • If the digit is 0, 1, or 8, we can continue the recursion without changing the ok status, as these digits do not alter the number's goodness by themselves.
  • If the digit is 2, 5, 6, or 9, we make the recursive call with ok set to True, since these digits ensure the number's goodness.

To avoid unnecessary calculations, we memoize the results of the recursive calls with different parameter combinations.

We structure the number n into an array a, where each element represents a digit in its corresponding place. Then we walk through the number's digits from the most significant digit to the least significant digit (right to left), calling our recursive function to sum up the counts of good numbers according to the above-defined rules.

The solution's effectiveness comes from carefully analyzing the properties of good numbers and utilizing recursive calls with caching to systematically count the valid numbers without enumerating them all.

Solution Approach

The provided Python solution makes use of recursion, dynamic programming through memoization, and digit-by-digit analysis to solve the problem of finding good integers within a given range.

Firstly, a recursive helper function dfs is defined. This function uses the following parameters:

  • pos: The current digit position we are filling in the potentially good integer.
  • ok: A boolean flag indicating whether we've already included at least one digit in the number that makes it 'good' upon rotation, such as 2, 5, 6, or 9.
  • limit: A flag that indicates whether the current digit being considered is constrained by the original integer n's corresponding digit.

The dfs function utilizes memoization to cache and reuse the results of the recursive calls, which prevents recalculating the same scenarios—this is done using the @cache decorator, which caches the results of the expensive function calls.

The recursive calls made by the dfs function follow these rules:

  • If pos is 0 or negative, it means we've looked at all digit positions, and we check the flag ok. If ok is true, we return 1 as we've found a good number; otherwise, we return 0 as the number does not meet the criterion.
  • Otherwise, we iterate over all possible digits from 0 to 9 (or up to the digit in the original number n if the limit is true), placing each digit in the current position and making a recursive call to dfs to decide the next position.
  • The current state of ok is passed on unless we're placing a digit that contributes to the goodness of the number (2, 5, 6, or 9), in which case ok is set to true for all deeper recursive calls.
  • The limit is only maintained if the digit being placed is equivalent to the corresponding digit in n.

To kick off the recursion, the original number n is broken down into its constituent digits and stored in an array a. This allows the function to easily compare each possible combination against n's corresponding digits to ensure validity.

Finally, the dfs function is called with the array length, ok set to 0 (as initially, we haven't placed any digits that would classify the integer as good), and limit set to True (because at the start, we are limited to n). The return value from this call gives the total number of good integers within the range specified.

This solution effectively parses the problem domain with a depth-first traversal, leveraging the constraints to prune the search space and using memoization to optimize the recursive exploration of possibilities, resulting in an efficient algorithm to find all good integers up to n.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we want to find all good integers up to n = 23. Using the definitions and rules from the solution approach, we would proceed as follows:

  1. We start by setting up our dfs function and decomposing our target integer n = 23 into an array a = [2, 3].

  2. We then call dfs(pos=len(a), ok=False, limit=True) to start the recursion, which implies we are starting from the digit in the tens place (as array indices are 0-based).

  3. At the first level of recursion (pos = 2), we have not yet placed any digit, so ok is False, and limit is True. We iterate over possible digits from 0 to 2 for the tens place since 2 is the tens digit of n (due to limit=True).

    • When we place a 0 or 1, we keep ok as False since these digits don't contribute to a number’s goodness. We also set limit to False for the next digit since we are already below n.
    • When we place a 2 (same as in n), we keep limit as True for the next digit to make sure we don't go over n. Here, we set ok to True because 2 contributes to the number’s goodness upon rotation (2 rotates to 5).
  4. Now, for the second level of recursion (pos = 1), we are checking the digit in the ones place. The limit flag instructs us whether we can consider digits up to 3 or all digits 0-9.

    • If we have placed a 0 or 1 in the tens place, we can consider all digits here, and if we place a 2, 5, 6, or 9, we set ok to True.
    • If we had placed a 2 in the tens place, we can go up to 3 in the ones place.
  5. Each time we reach pos = 0 (the base case), we check if ok is True, meaning we have made the number good. If so, we return 1; otherwise, we return 0.

  6. Finally, after considering all possibilities for each digit, the sum of all recursive call returns will give us the count of good integers. In our case, we would find the valid good numbers to be 2, 5, 6, 8, 9, 20, 21, 22, and 25. Numbers like 11, 12, 15, 18, and 19 are not counted because they are beyond n.

Thus, we've walked through this approach to find there are 9 good integers between 1 and 23.

Python Solution

1from functools import lru_cache
2
3class Solution:
4    def rotatedDigits(self, N: int) -> int:
5        # A helper function that uses depth-first search to determine
6        # the valid numbers according to the problem constraints.
7        @lru_cache(maxsize=None)
8        def dfs(position, is_good, is_limit):
9            # Base case: if position is zero, return 1 if 'is_good' is True,
10            # because we've found a valid number, and 0 otherwise.
11            if position == 0:
12                return 1 if is_good else 0
13          
14            # If 'is_limit' is True, we can only go up to 'digits[position]'
15            # otherwise, we can use digits 0-9.
16            upper_bound = digits[position] if is_limit else 9
17          
18            # This will accumulate the number of valid numbers found.
19            valid_numbers = 0
20          
21            # Iterate through the possible digits at this position.
22            for digit in range(upper_bound + 1):  
23                # Digits 0, 1, and 8 do not change the number's validity
24                if digit in (0, 1, 8):
25                    valid_numbers += dfs(position - 1, is_good, is_limit and digit == upper_bound)
26                # Digits 2, 5, 6, and 9 make the number valid if it wasn't already
27                elif digit in (2, 5, 6, 9):
28                    valid_numbers += dfs(position - 1, 1, is_limit and digit == upper_bound)
29          
30            return valid_numbers
31
32        # Convert the number to a list of its digits in reversed order.
33        # Allocate enough space for digits (here it's 6 for some reason, 
34        # but we could dynamically determine this based on the size of N).
35        digits = [0] * 6
36        length = 1
37        while N:
38            digits[length] = N % 10
39            N //= 10
40            length += 1
41      
42        # Call the helper function 'dfs' with the current length of the number,
43        # the initial state of 'is_good' as False, and 'is_limit' as True,
44        # because we are starting with the actual limit of N.
45        return dfs(length, 0, True)
46

Java Solution

1class Solution {
2
3    // Member variable to hold digits of the number
4    private int[] digits = new int[6];
5  
6    // DP cache to store intermediate results, initialized to -1 indicating uncomputed states
7    private int[][] dpCache = new int[6][2]; 
8
9    public int rotatedDigits(int n) {
10        int length = 0; // Will keep track of the number of digits
11      
12        // Initialize the dpCache array with -1, except where it's been computed already
13        for (int[] row : dpCache) {
14            Arrays.fill(row, -1);
15        }
16      
17        // Backfill the array 'digits' with individual digits of the number n
18        while (n > 0) {
19            digits[++length] = n % 10; // Store each digit
20            n /= 10; // Reduce n by a factor of 10
21        }
22      
23        // Start the depth-first search from most significant digit with 'ok' as false and limit as true
24        return depthFirstSearch(length, 0, true);
25    }
26
27    private int depthFirstSearch(int position, int countValid, boolean limit) {
28        if (position <= 0) {
29            // Base case: when all positions are processed, check if we
30            // have at least one valid digit (2, 5, 6, or 9)
31            return countValid;
32        }
33      
34        // Check the DP cache to avoid re-computation unless we're limited by the current value
35        if (!limit && dpCache[position][countValid] != -1) {
36            return dpCache[position][countValid];
37        }
38      
39        // Calculate the upper bound for this digit. If we have a limit, we cannot exceed the given digit
40        int upperBound = limit ? digits[position] : 9;
41        int ans = 0; // To store the number of valid numbers
42      
43        for (int i = 0; i <= upperBound; ++i) {
44            if (i == 0 || i == 1 || i == 8) {
45                // Digits 0, 1, and 8 are valid but not counted towards 'countValid' flag
46                ans += depthFirstSearch(position - 1, countValid, limit && i == upperBound);
47            }
48            if (i == 2 || i == 5 || i == 6 || i == 9) {
49                // Digits 2, 5, 6, and 9 are valid and counted towards 'countValid' flag
50                ans += depthFirstSearch(position - 1, 1, limit && i == upperBound);
51            }
52        }
53      
54        // Cache the computed value if there was no limit
55        if (!limit) {
56            dpCache[position][countValid] = ans;
57        }
58        return ans; // Return the calculated number of valid rotated digits
59    }
60}
61

C++ Solution

1class Solution {
2public:
3    int digits[6];        // Array to store the digits of the number n
4    int memo[6][2];       // Memoization table for dynamic programming
5
6    // Main function that initiates the process and returns the count of good numbers
7    int rotatedDigits(int n) {
8        memset(memo, -1, sizeof(memo)); // Initialize the memoization table with -1
9        int length = 0;                 // Used to store the number of digits in n
10        // Extract the digits of n and store them in reverse order in the array 'digits'
11        while (n) {
12            digits[++length] = n % 10;
13            n /= 10;
14        }
15        // Start the DFS from the most significant digit with the condition that it has not
16        // encountered a different good digit yet (ok = 0) and that it is the initial limit
17        return depthFirstSearch(length, 0, true);
18    }
19
20    // Recursive function to count the good numbers
21    int depthFirstSearch(int position, int hasDiffGoodDigit, bool isLimit) {
22        // If we have no more digits to process and we have encountered a good digit different
23        // from 0, 1, 8, return 1 as this is a good number
24        if (position == 0) {
25            return hasDiffGoodDigit;
26        }
27        // Use memoization to avoid recalculating states we have already seen
28        if (!isLimit && memo[position][hasDiffGoodDigit] != -1) {
29            return memo[position][hasDiffGoodDigit];
30        }
31        // Determine the upper bound for the digit that we can place at the current position
32        int upperLimit = isLimit ? digits[position] : 9;
33        int count = 0; // Initialize count of good numbers
34        // Iterate through possible digits
35        for (int i = 0; i <= upperLimit; ++i) {
36            // If the digit is 0, 1, or 8, we continue the search without changing the state
37            if (i == 0 || i == 1 || i == 8) {
38                count += depthFirstSearch(position - 1, hasDiffGoodDigit, isLimit && i == upperLimit);
39            }
40            // If the digit is 2, 5, 6, or 9, we continue the search and mark the state as having
41            // encountered a different good digit
42            if (i == 2 || i == 5 || i == 6 || i == 9) {
43                count += depthFirstSearch(position - 1, 1, isLimit && i == upperLimit);
44            }
45        }
46        // If we are not at the limit, update the memoization table
47        if (!isLimit) {
48            memo[position][hasDiffGoodDigit] = count;
49        }
50        // Return the count of good numbers for the current digit position and state
51        return count;
52    }
53};
54

Typescript Solution

1// TypeScript does not require specifying the size of array beforehand like C++
2let digits: number[] = [];
3// Initialize memoization array with undefined values since TypeScript doesn't have memset
4let memo: number[][] = Array.from({ length: 6 }, () => Array(2).fill(undefined));
5
6// Function to initialize the process and return the count of good numbers
7function rotatedDigits(n: number): number {
8    // Reset memoization array
9    memo.forEach(row => row.fill(undefined));
10    let length = 0;
11    // Extract the digits of n and store them in reverse order in 'digits' array
12    while (n > 0) {
13        digits[length++] = n % 10;
14        n = Math.floor(n / 10);
15    }
16    // Start the DFS from the most significant digit
17    return depthFirstSearch(length, 0, true);
18}
19
20// Recursive function to count the good numbers
21function depthFirstSearch(position: number, hasDiffGoodDigit: number, isLimit: boolean): number {
22    // Base case: if no digits left and a different good digit has been found
23    if (position === 0) {
24        return hasDiffGoodDigit;
25    }
26    // Check memo table to possibly use previously calculated result
27    if (!isLimit && memo[position][hasDiffGoodDigit] !== undefined) {
28        return memo[position][hasDiffGoodDigit];
29    }
30    let upperLimit = isLimit ? digits[position - 1] : 9; // fixing off-by-one error from original code
31    let count = 0;
32    // Iterate through all possible digits for the current position
33    for (let i = 0; i <= upperLimit; i++) {
34        // Good digits that are the same when rotated
35        if (i === 0 || i === 1 || i === 8) {
36            count += depthFirstSearch(position - 1, hasDiffGoodDigit, isLimit && i === upperLimit);
37        }
38        // Digits that become different good digits when rotated
39        else if (i === 2 || i === 5 || i === 6 || i === 9) {
40            count += depthFirstSearch(position - 1, 1, isLimit && i === upperLimit);
41        }
42    }
43    // Memoize result if not at a limit
44    if (!isLimit) {
45        memo[position][hasDiffGoodDigit] = count;
46    }
47    return count;
48}
49

Time and Space Complexity

The given code defines a function rotatedDigits which takes an integer n and returns the count of numbers less than or equal to n where the digits 2, 5, 6, or 9 appear at least once (making the number 'good'), and the digits 3, 4, or 7 do not appear at all (since they cannot be rotated to a valid number). It does not include numbers that remain the same after being rotated.

Time Complexity

The time complexity of the modified code is O(logN * 4^logN) which simplifies to O(N^2) where N is the number of digits in the input number n. This is because there are logN digits in n, and for each digit position, we iterate over up to 4 possible 'good' digits. There is a factor of logN for each digit position since there are that many recursive calls at each level, considering that limit is set to True only when i == up which means the next function call will honour the limit created by the previous digit.

Using memoization with @cache, we avoid repetitive calculations for each unique combination of the position of the digit, the flag whether we have encountered a 'good' digit, and whether we are limited by the original number's digit at this position (up) which leads to pruning the search space significantly.

Space Complexity

The space complexity of the code is O(logN * 2 * logN) which simplifies to O((logN)^2).

This includes space for:

  • The memoization cache which could potentially store all states of the function arguments (pos, ok, limit).
  • The array a of length 6, indicating the input number is decomposed into up to 6 digits, accounting for integers up to a maximum of 999999. However, this 6 is a constant and does not scale with the input, so it does not affect the time complexity.

Therefore, the space used by the recursion stack and the memoization dictionary depends on the number of different states the dfs function can be in, which is influenced by the number of digits logN (representing different positions) and the boolean flags ok and limit, leading to the complexity of O((logN)^2).

😈
Become an
Algo Monster

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 👨‍🏫