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
, and8
rotate to themselves.2
and5
can rotate to each other.6
and9
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 numbern
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.
Learn more about Math and Dynamic Programming patterns.
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 as2
,5
,6
, or9
.limit
: A flag that indicates whether the current digit being considered is constrained by the original integern
'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 flagok
. Ifok
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 thelimit
is true), placing each digit in the current position and making a recursive call todfs
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 caseok
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 inn
.
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
We start by setting up our
dfs
function and decomposing our target integern = 23
into an arraya = [2, 3]
. -
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). -
At the first level of recursion (
pos = 2
), we have not yet placed any digit, sook
isFalse
, andlimit
isTrue
. We iterate over possible digits from 0 to 2 for the tens place since 2 is the tens digit ofn
(due tolimit=True
).- When we place a
0
or1
, we keepok
asFalse
since these digits don't contribute to a number’s goodness. We also setlimit
toFalse
for the next digit since we are already belown
. - When we place a
2
(same as inn
), we keeplimit
asTrue
for the next digit to make sure we don't go overn
. Here, we setok
toTrue
because2
contributes to the number’s goodness upon rotation (2 rotates to 5).
- When we place a
-
Now, for the second level of recursion (
pos = 1
), we are checking the digit in the ones place. Thelimit
flag instructs us whether we can consider digits up to3
or all digits 0-9.- If we have placed a
0
or1
in the tens place, we can consider all digits here, and if we place a2
,5
,6
, or9
, we setok
toTrue
. - If we had placed a
2
in the tens place, we can go up to3
in the ones place.
- If we have placed a
-
Each time we reach
pos = 0
(the base case), we check ifok
isTrue
, meaning we have made the number good. If so, we return1
; otherwise, we return0
. -
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
, and25
. Numbers like11
,12
,15
,18
, and19
are not counted because they are beyondn
.
Thus, we've walked through this approach to find there are 9 good integers between 1 and 23.
Solution Implementation
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
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
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
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 length6
, indicating the input number is decomposed into up to6
digits, accounting for integers up to a maximum of999999
. However, this6
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)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we