Rotated Digits

Med

#0742Time: O(log n). The number of states is `length * 2 * 2`, where `length` is `O(log n)`. Each state is computed once due to memoization.Space: O(log n). The space is dominated by the memoization table, which has a size proportional to the number of digits in `n`, and the recursion stack depth.1 company

Patterns

Math Dynamic Programming

Companies

Arista Networks

Prompt

An integer x is a good if after rotating each digit individually by 180 degrees, we get a valid number that is different from x. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. For example:

0, 1, and 8 rotate to themselves,
2 and 5 rotate to each other (in this case they are rotated in a different direction, in other words, 2 or 5 gets mirrored),
6 and 9 rotate to each other, and
the rest of the numbers do not rotate to any other number and become invalid.

Given an integer n, return the number of good integers in the range [1, n].

Example 1:

Input: n = 10
Output: 4
Explanation: There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Example 2:

Input: n = 1
Output: 0

Example 3:

Input: n = 2
Output: 1

Constraints:

1 <= n <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

A highly efficient method using Digit Dynamic Programming (DP). Instead of checking each number individually, this approach constructs the count of "good" numbers by considering the digits of n from left to right. It counts the number of valid combinations of digits that can form a good number up to n.

Algorithm

Convert the input n into a string S.
Create a 3D memoization table memo[S.length()][2][2] to store results of subproblems, avoiding re-computation.
Define a recursive function solve(index, isTight, hasChangingDigit):
- index: The current digit position we are filling (from left to right).
- isTight: A boolean indicating if our choices are limited by the digits of S.
- hasChangingDigit: A boolean indicating if a digit like 2, 5, 6, or 9 has been used.
Base Case: If index equals the length of S, we have formed a complete number. Return 1 if hasChangingDigit is true, otherwise 0.
Recursive Step: a. Determine the upper bound for the current digit's loop (either S[index] if isTight is true, or 9 otherwise). b. Iterate from digit d = 0 to the upperBound. c. Skip invalid digits 3, 4, 7. d. For each valid digit d, make a recursive call: solve(index + 1, newTight, newHasChangingDigit). e. Update newTight and newHasChangingDigit based on the current digit d. f. Sum the results of the recursive calls.
Store the result in the memoization table before returning.
The initial call to start the process is solve(0, true, false).

Walkthrough

This approach rephrases the problem as "count the numbers up to n that contain at least one digit from {2, 5, 6, 9} and no digits from {3, 4, 7}". We can solve this using a recursive function with memoization.

Let's define a function solve(index, isTight, hasChangingDigit) that counts the number of ways to complete a valid number from the current state.

index: The current digit position (from left) we are placing.
isTight: A boolean flag. true if we are restricted by the digits of n (i.e., we can't place a digit greater than n's digit at this position). It becomes false once we place a digit smaller than n's corresponding digit.
hasChangingDigit: A boolean flag that is true if we have already placed a digit from {2, 5, 6, 9}.

The recursion explores all possible digits at the current index. For each valid choice, it calls itself for the next index with updated isTight and hasChangingDigit flags. The base case is when we have placed all digits; we return 1 if hasChangingDigit is true (indicating a good number) and 0 otherwise. A memoization table stores the results for each state (index, isTight, hasChangingDigit) to prevent re-computation.

1import java.util.Arrays;2 3class Solution {4    private int[][][] memo;5    private String s;6 7    public int rotatedDigits(int n) {8        s = String.valueOf(n);9        memo = new int[s.length()][2][2];10        for (int[][] a2 : memo) {11            for (int[] a1 : a2) {12                Arrays.fill(a1, -1);13            }14        }15        return solve(0, true, false);16    }17 18    // Returns the count of good numbers that can be formed from this state up to N19    private int solve(int index, boolean isTight, boolean hasChangingDigit) {20        // Base case: we have successfully constructed a number.21        if (index == s.length()) {22            return hasChangingDigit ? 1 : 0;23        }24 25        // Memoization check26        if (memo[index][isTight ? 1 : 0][hasChangingDigit ? 1 : 0] != -1) {27            return memo[index][isTight ? 1 : 0][hasChangingDigit ? 1 : 0];28        }29 30        int count = 0;31        int upperBound = isTight ? (s.charAt(index) - '0') : 9;32 33        for (int d = 0; d <= upperBound; d++) {34            // Skip digits that make the number invalid upon rotation.35            if (d == 3 || d == 4 || d == 7) {36                continue;37            }38 39            // The new number is still tightly bound only if the original was tight40            // and we are choosing the maximum possible digit.41            boolean newTight = isTight && (d == upperBound);42 43            // The new number has a changing digit if the original did, or if the current digit is a changing one.44            boolean newHasChangingDigit = hasChangingDigit || (d == 2 || d == 5 || d == 6 || d == 9);45 46            count += solve(index + 1, newTight, newHasChangingDigit);47        }48 49        return memo[index][isTight ? 1 : 0][hasChangingDigit ? 1 : 0] = count;50    }51}

Complexity

Time

O(log n). The number of states is `length * 2 * 2`, where `length` is `O(log n)`. Each state is computed once due to memoization.

Space

O(log n). The space is dominated by the memoization table, which has a size proportional to the number of digits in `n`, and the recursion stack depth.

Trade-offs

Pros

Extremely efficient, with a time complexity logarithmic in n.
Scales to much larger constraints on n where brute-force would be too slow.

Cons

Significantly more complex to understand and implement correctly.
The overhead of recursion and memoization might make it slightly slower for very small n compared to the simple loop, though its asymptotic complexity is superior.

This approach involves iterating through every number from 1 to n and, for each number, determining if it meets the criteria of a "good" number. A helper function is typically used to encapsulate the logic for checking a single number.

Algorithm

Initialize a counter count to 0.
Iterate through each integer i from 1 to n.
For each i, call a helper function isGood(i) to check if it's a "good" number.
The isGood(num) function works as follows: a. Convert the number num to its string representation. b. Initialize a boolean flag isDifferent to false. c. Iterate through each character (digit) c of the string. d. If c is '3', '4', or '7', the number is invalid. Return false immediately. e. If c is '2', '5', '6', or '9', set isDifferent to true. f. After checking all digits, if the number was valid throughout the loop, return the final value of isDifferent.
If isGood(i) returns true, increment count.
After the loop finishes, return count.

Walkthrough

The core of this method is a loop that runs from 1 to n. Inside this loop, we check each number i for two properties:

Validity: The number must only contain digits that are valid after a 180-degree rotation. These are 0, 1, 8, 2, 5, 6, 9. If any digit is 3, 4, or 7, the number is immediately disqualified.
Difference: The rotated number must be different from the original. This happens if the number contains at least one digit that rotates to a different digit, i.e., 2, 5, 6, 9. Digits 0, 1, 8 rotate to themselves.

We can implement a helper function, isGood(num), that checks these two conditions. It can convert the number to a string and iterate through its digits. A flag can track whether a "changing" digit (2, 5, 6, 9) has been found. If an invalid digit (3, 4, 7) is encountered, the function returns false. If the loop completes, the function returns true only if the flag for a changing digit was set.

1class Solution {2    public int rotatedDigits(int n) {3        int count = 0;4        for (int i = 1; i <= n; i++) {5            if (isGood(i)) {6                count++;7            }8        }9        return count;10    }11 12    /**13     * A number is good if it's valid and different after rotation.14     * - Valid means it only contains digits {0, 1, 2, 5, 6, 8, 9}.15     * - Different means it must contain at least one of {2, 5, 6, 9}.16     */17    private boolean isGood(int num) {18        boolean isDifferent = false;19        String s = String.valueOf(num);20        for (char c : s.toCharArray()) {21            if (c == '3' || c == '4' || c == '7') {22                return false; // Contains an invalid digit23            }24            if (c == '2' || c == '5' || c == '6' || c == '9') {25                isDifferent = true; // Contains a digit that changes the number26            }27        }28        return isDifferent;29    }30}

Complexity

Time

O(n * log n). We iterate through `n` numbers. For each number, we process its digits. The number of digits in an integer `x` is approximately `log10(x)`.

Space

O(log n). The space required is to store the string representation of the current number, which has a length proportional to the number of digits in `n`.

Trade-offs

Pros

Simple to understand and implement.
Sufficiently fast for the given constraints (n <= 10^4).

Cons

Less efficient than dynamic programming, especially for larger values of n.
Performs redundant work by re-evaluating digits for different numbers.

Solutions

Solution

1class Solution {2private3  int[] a = new int[6];4private5  int[][] dp = new int[6][2];6public7  int rotatedDigits(int n) {8    int len = 0;9    for (var e : dp) {10      Arrays.fill(e, -1);11    }12    while (n > 0) {13      a[++len] = n % 10;14      n /= 10;15    }16    return dfs(len, 0, true);17  }18private19  int dfs(int pos, int ok, boolean limit) {20    if (pos <= 0) {21      return ok;22    }23    if (!limit && dp[pos][ok] != -1) {24      return dp[pos][ok];25    }26    int up = limit ? a[pos] : 9;27    int ans = 0;28    for (int i = 0; i <= up; ++i) {29      if (i == 0 || i == 1 || i == 8) {30        ans += dfs(pos - 1, ok, limit && i == up);31      }32      if (i == 2 || i == 5 || i == 6 || i == 9) {33        ans += dfs(pos - 1, 1, limit && i == up);34      }35    }36    if (!limit) {37      dp[pos][ok] = ans;38    }39    return ans;40  }41}

1class Solution {2public:3  int a[6];4  int dp[6][2];5  int rotatedDigits(int n) {6    memset(dp, -1, sizeof dp);7    int len = 0;8    while (n) {9      a[++len] = n % 10;10      n /= 10;11    }12    return dfs(len, 0, true);13  }14  int dfs(int pos, int ok, bool limit) {15    if (pos <= 0) {16      return ok;17    }18    if (!limit && dp[pos][ok] != -1) {19      return dp[pos][ok];20    }21    int up = limit ? a[pos] : 9;22    int ans = 0;23    for (int i = 0; i <= up; ++i) {24      if (i == 0 || i == 1 || i == 8) {25        ans += dfs(pos - 1, ok, limit && i == up);26      }27      if (i == 2 || i == 5 || i == 6 || i == 9) {28        ans += dfs(pos - 1, 1, limit && i == up);29      }30    }31    if (!limit) {32      dp[pos][ok] = ans;33    }34    return ans;35  }36};

1class Solution:2    def rotatedDigits(self, n: int) -> int: @ cache def dfs(pos, ok, limit): if pos <= 0: return ok up = a[pos] if limit else 9 ans = 0 for i in range(up + 1): if i in (0, 1, 8): ans += dfs(pos - 1, ok, limit and i == up) if i in (2, 5, 6, 9): ans += dfs(pos - 1, 1, limit and i == up) return ans a = [0] * 6 l = 1 while n: a[l] = n % 10 n //= 10 l += 1 return dfs(l, 0, True)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem