Rotated Digits

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.

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).

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.

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;
    }
}