Problem Description
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. Given an integer n, return the number of good integers in the range [1, n].
Key Insights
- The digits 0, 1, and 8 remain the same after rotation.
- The digits 2 and 5 rotate to each other.
- The digits 6 and 9 rotate to each other.
- Digits 3, 4, and 7 do not produce valid digits upon rotation.
- A good number must not remain unchanged after rotation.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve the problem, we will iterate through each number from 1 to n and check if it is a good number. For each digit in the number, we will determine if it can produce a valid rotated digit. We will maintain a count of good numbers and return this count at the end of our iteration.
We will use a set to keep track of valid and good digits. The algorithm will check each digit of the number, and if all digits are valid but not all remain unchanged, we classify the number as good.