# Rotated Digits
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rotated-digits)
Canonical: https://scaleengineer.com/dsa/problems/rotated-digits
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## Problem
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 <= 104`

# Approaches
## Brute-Force Iteration
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.
**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`.
**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.
### Explanation
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:

1.  **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.
2.  **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.

```java
class Solution {
    public int rotatedDigits(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isGood(i)) {
                count++;
            }
        }
        return count;
    }

    /**
     * A number is good if it's valid and different after rotation.
     * - Valid means it only contains digits {0, 1, 2, 5, 6, 8, 9}.
     * - Different means it must contain at least one of {2, 5, 6, 9}.
     */
    private boolean isGood(int num) {
        boolean isDifferent = false;
        String s = String.valueOf(num);
        for (char c : s.toCharArray()) {
            if (c == '3' || c == '4' || c == '7') {
                return false; // Contains an invalid digit
            }
            if (c == '2' || c == '5' || c == '6' || c == '9') {
                isDifferent = true; // Contains a digit that changes the number
            }
        }
        return isDifferent;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Iterate through each integer `i` from 1 to `n`.
3. For each `i`, call a helper function `isGood(i)` to check if it's a "good" number.
4. 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`.
5. If `isGood(i)` returns `true`, increment `count`.
6. After the loop finishes, return `count`.

## Digit Dynamic Programming
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`.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    private int[][][] memo;
    private String s;

    public int rotatedDigits(int n) {
        s = String.valueOf(n);
        memo = new int[s.length()][2][2];
        for (int[][] a2 : memo) {
            for (int[] a1 : a2) {
                Arrays.fill(a1, -1);
            }
        }
        return solve(0, true, false);
    }

    // Returns the count of good numbers that can be formed from this state up to N
    private int solve(int index, boolean isTight, boolean hasChangingDigit) {
        // Base case: we have successfully constructed a number.
        if (index == s.length()) {
            return hasChangingDigit ? 1 : 0;
        }

        // Memoization check
        if (memo[index][isTight ? 1 : 0][hasChangingDigit ? 1 : 0] != -1) {
            return memo[index][isTight ? 1 : 0][hasChangingDigit ? 1 : 0];
        }

        int count = 0;
        int upperBound = isTight ? (s.charAt(index) - '0') : 9;

        for (int d = 0; d <= upperBound; d++) {
            // Skip digits that make the number invalid upon rotation.
            if (d == 3 || d == 4 || d == 7) {
                continue;
            }

            // The new number is still tightly bound only if the original was tight
            // and we are choosing the maximum possible digit.
            boolean newTight = isTight && (d == upperBound);

            // The new number has a changing digit if the original did, or if the current digit is a changing one.
            boolean newHasChangingDigit = hasChangingDigit || (d == 2 || d == 5 || d == 6 || d == 9);

            count += solve(index + 1, newTight, newHasChangingDigit);
        }

        return memo[index][isTight ? 1 : 0][hasChangingDigit ? 1 : 0] = count;
    }
}
```
### Algorithm
1. Convert the input `n` into a string `S`.
2. Create a 3D memoization table `memo[S.length()][2][2]` to store results of subproblems, avoiding re-computation.
3. 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.
4. **Base Case:** If `index` equals the length of `S`, we have formed a complete number. Return `1` if `hasChangingDigit` is true, otherwise `0`.
5. **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.
6. Store the result in the memoization table before returning.
7. The initial call to start the process is `solve(0, true, false)`.

# Solutions
### Java

```java
class Solution {
private
  int[] a = new int[6];
private
  int[][] dp = new int[6][2];
public
  int rotatedDigits(int n) {
    int len = 0;
    for (var e : dp) {
      Arrays.fill(e, -1);
    }
    while (n > 0) {
      a[++len] = n % 10;
      n /= 10;
    }
    return dfs(len, 0, true);
  }
private
  int dfs(int pos, int ok, boolean limit) {
    if (pos <= 0) {
      return ok;
    }
    if (!limit && dp[pos][ok] != -1) {
      return dp[pos][ok];
    }
    int up = limit ? a[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up; ++i) {
      if (i == 0 || i == 1 || i == 8) {
        ans += dfs(pos - 1, ok, limit && i == up);
      }
      if (i == 2 || i == 5 || i == 6 || i == 9) {
        ans += dfs(pos - 1, 1, limit && i == up);
      }
    }
    if (!limit) {
      dp[pos][ok] = ans;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int a[6];
  int dp[6][2];
  int rotatedDigits(int n) {
    memset(dp, -1, sizeof dp);
    int len = 0;
    while (n) {
      a[++len] = n % 10;
      n /= 10;
    }
    return dfs(len, 0, true);
  }
  int dfs(int pos, int ok, bool limit) {
    if (pos <= 0) {
      return ok;
    }
    if (!limit && dp[pos][ok] != -1) {
      return dp[pos][ok];
    }
    int up = limit ? a[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up; ++i) {
      if (i == 0 || i == 1 || i == 8) {
        ans += dfs(pos - 1, ok, limit && i == up);
      }
      if (i == 2 || i == 5 || i == 6 || i == 9) {
        ans += dfs(pos - 1, 1, limit && i == up);
      }
    }
    if (!limit) {
      dp[pos][ok] = ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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)

```