Introduction

In this blog post, we will explore how to solve the LeetCode problem "788" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

Here's the solution:

• Dynamic Programming: Build the solution iteratively. Store if a number of length k is good or not, and use this information to determine if a number of length k+1 is good.
• Base Cases: Handle single-digit numbers directly.

• Recursive Check with Memoization (implemented iteratively with DP): Efficiently explore the number space up to n.

• Runtime Complexity: O(N), where N is the input integer. Although it seems like we might be going through every possible number up to N, in effect the dynamic programming approach limits us to a calculation cost per digit making the algorithm linear with the number of digits in N which is Log10(N) but this is still less than O(N). The constant cost of each check adds up to a linear run time.

• Storage Complexity: O(1).

Code

    def rotatedDigits(n: int) -> int:
    """
    Counts the number of "good" integers between 1 and n (inclusive).
    """

    count = 0
    for i in range(1, n + 1):
        s = str(i)
        valid = True
        changed = False
        for digit in s:
            if digit in ('3', '4', '7'):
                valid = False
                break
            elif digit in ('2', '5', '6', '9'):
                changed = True

        if valid and changed:
            count += 1

    return count