788. Rotated Digits

Problem Statement in English

You’re given a positive integer n. A number is considered a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from the original number. Each digit must be rotated - we cannot choose to leave it alone.

• 0, 1, and 8 rotate to themselves
• 2 and 5 rotate to each other
• 6 and 9 rotate to each other
• the rest of the digits do not rotate to any other number and become invalid.

Return the number of good integers in the range [1, n].

Approach

We can use dynamic programming to solve this problem. We will create a dp array where dp[i] will represent the state of the number i. The state can be:

• 0: if the number is invalid
• 1: if the number is valid but not good
• 2: if the number is good

We will iterate through all the numbers from $0$ to $n$ and fill the dp array based on the rules given in the problem statement. Finally, we will count how many numbers are good (i.e., have a state of 2).

For each number we take its last digit (let’s call it b) and the number formed by the remaining digits (let’s call it a). The state of the number will depend on the states of a and b. Note that since we’re iterating forwards, we would have already computed the states for a and b when we reach the number i.8

If a and b respectfully are:

• 1 and 1: then the number is valid but not good (state 1)

• = 1 and >= 1: then the number is good (state 2), and we increment our count of good numbers by 1

• else: the number is invalid (state 0)

We fill up the dp array using the above rules and return the count of good numbers.

And we’re done!

Solution in Python

class Solution:
    def rotatedDigits(self, n: int) -> int:
        dp = [0] * (n + 1)
        count = 0

        for i in range(n + 1):
            if i < 10:
                if i in (0, 1, 8):
                    dp[i] = 1
                elif i in (2, 5, 6, 9):
                    dp[i] = 2
                    count += 1
                else:
                    dp[i] = 0
            else:
                a = dp[i // 10]
                b = dp[i % 10]

                if a == 1 and b == 1:
                    dp[i] = 1
                elif a >= 1 and b >= 1:
                    dp[i] = 2
                    count += 1
                else:
                    dp[i] = 0

        return count

Complexity

• Time: $O(n)$
  Since we iterate through all the numbers from 0 to n.

• Space: $O(n)$
  Since we use a dp array of size n + 1.

Mistakes I Made

I had to look this up :(

And we are done.