algoadvance

Leetcode 788. Rotated Digits

Problem Statement

788. Rotated Digits

X is a good number if after rotating each digit individually by 180 degrees, we get a valid digit and the result is different from X. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit becomes another digit after rotation, where the digits are:

• 0 rotates to 0
• 1 rotates to 1
• 8 rotates to 8
• 2 rotates to 5
• 5 rotates to 2
• 6 rotates to 9
• 9 rotates to 6

However, the digits 3, 4, and 7 are not valid after rotation.

Given an integer N, return the number of good numbers in the range [1, N].

Example

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

Clarifying Questions

1. Is the input N always a positive integer?
   • Yes, you can assume that N is a positive integer.
2. Are there any constraints on the value of N?
   • The problem statement does not specify, but typical constraints for similar problems range up to 10,000.
3. Do we need to handle any edge cases such as zero?
   • No, since N is always positive, we do not need to handle zero.
4. How should we handle large values of N in terms of performance?
   • We should aim for an efficient solution, ideally linear in complexity given the constraints.

Strategy

1. Initialization: Create a map or method to transform digits according to the 180-degree rotation rules.
2. Validation: Define a method to check if a number is a ‘good number’ by validating each digit.
3. Count Good Numbers: Iterate from 1 to N, checking if each number is good and count them.

Pseudocode

1. Create a list or set of valid digits that transform into other valid digits.
2. Create a method isGoodNumber to check the validity of each number.
3. Iterate through the numbers from 1 to N and use isGoodNumber to count how many are good.

Code

public class RotatedDigits {
    public int rotatedDigits(int N) {
        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (isGoodNumber(i)) {
                count++;
            }
        }
        return count;
    }

    private boolean isGoodNumber(int n) {
        boolean isValid = false;
        while (n > 0) {
            int d = n % 10;
            if (d == 3 || d == 4 || d == 7) {
                return false;
            }
            if (d == 2 || d == 5 || d == 6 || d == 9) {
                isValid = true;
            }
            n /= 10;
        }
        return isValid;
    }

    public static void main(String[] args) {
        RotatedDigits solution = new RotatedDigits();
        System.out.println(solution.rotatedDigits(10));  // Output: 4
    }
}

Time Complexity

• Time Complexity: O(N * d), where d is the number of digits in the number. In the worst case, this can be considered approximately O(N log N).
• Space Complexity: O(1), since we are using a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?