Brute Force Solution

A naive solution would be to iterate through all numbers from 1 to n and check for each number if it is a good number. A number is good if, after rotating each digit individually by 180 degrees, we get a valid number that is different from the original number.

Algorithm

1. Iterate from 1 to n.
2. For each number x, convert it to a string.
3. Rotate each digit. If any digit is invalid after rotation, the number is not good.
4. If all digits are valid after rotation, reconstruct the rotated number.
5. If the rotated number is different from the original number, increment the count of good numbers.

Code (Python)

def is_good(n):
    s = str(n)
    rotated = ''
    for digit in s:
        if digit == '0':
            rotated += '0'
        elif digit == '1':
            rotated += '1'
        elif digit == '2':
            rotated += '5'
        elif digit == '5':
            rotated += '2'
        elif digit == '6':
            rotated += '9'
        elif digit == '8':
            rotated += '8'
        elif digit == '9':
            rotated += '6'
        else:
            return False
    return rotated != s

def count_good_numbers_brute_force(n):
    count = 0
    for i in range(1, n + 1):
        if is_good(i):
            count += 1
    return count

Big O Analysis

• Time Complexity: O(n * log(n)). For each number from 1 to n, we are doing a string conversion and a linear scan of digits. The number of digits of n is log(n).
• Space Complexity: O(log(n)). We store the string representation of the rotated number, whose length is the number of digits in n.

Optimal Solution - Dynamic Programming

An optimal solution involves dynamic programming. We can build the solution based on the length of the number. We can count the numbers of length i which are good. A number is good if it contains at least one of the digits 2, 5, 6, or 9. These numbers are "rotating" numbers. Other digits such as 0, 1, and 8 are "self-rotating" numbers.

Algorithm

1. Define dp[i][0] as the number of "good" numbers of length i (containing at least one of 2, 5, 6, 9).
2. Define dp[i][1] as the number of all "valid" numbers of length i (containing only 0, 1, 2, 5, 6, 8, 9).
3. Base case: dp[0][0] = 0, dp[1][0] = 4 (2, 5, 6, 9), dp[1][1] = 7 (0, 1, 2, 5, 6, 8, 9). Note that dp[0][1] does not exist and is undefined. The reason is we cannot have a zero length number. However, for convenience, we can assume dp[0][1] = 1.
4. Recursive relation:
   • dp[i][1] = dp[i-1][1] * 7 (each digit can be any of 0, 1, 2, 5, 6, 8, 9).
   • dp[i][0] = dp[i-1][0] * 7 + dp[i-1][1] * 4 (the "good" numbers can be formed by either adding a "safe" digit to a "good" number, or adding a "good" digit (2, 5, 6, 9) to a "safe" number).
5. Now, consider the input n. Let s be the string representation of n. We can iterate through the digits of s to calculate the count of good numbers.
6. The count will be determined by two parts: (a) good numbers with length less than the length of n, (b) good numbers with length equal to the length of n.

Code (Python)

def count_good_numbers(n):
    s = str(n)
    length = len(s)
    dp = [[0, 0] for _ in range(length + 1)]
    dp[0][1] = 1
    for i in range(1, length + 1):
        dp[i][1] = dp[i - 1][1] * 7
        dp[i][0] = dp[i - 1][0] * 7 + dp[i - 1][1] * 4

    ans = 0
    safe = True
    for i, digit in enumerate(s):
        digit = int(digit)
        if safe:
            if i < length - 1:
                if digit >= 0:  # 0 is valid
                    ans += dp[length - 1 - i][0]
                if digit >= 2:
                    ans += dp[length - 1 - i][1]
                if digit >= 5:
                    ans += dp[length - 1 - i][1]
                if digit >= 6:
                    ans += dp[length - 1 - i][1]
                if digit >= 9:
                    ans += dp[length - 1 - i][1]

            if digit in [0, 1, 8]:
                pass
            elif digit in [2, 5, 6, 9]:
                ans += 0 # This is important
            else:
                safe = False
                break
        if i == length - 1 and safe:
            if digit in [2, 5, 6, 9]:
                ans += 1

    return ans

Big O Analysis

• Time Complexity: O(log(n)). The loop iterates through the digits of n, and the number of digits is log(n).
• Space Complexity: O(log(n)). The dp table stores log(n) elements.

Edge Cases

• n = 1, Output = 0
• n = 2, Output = 1
• n = 10, Output = 4