algoadvance

Leetcode 788. Rotated Digits

Problem Statement

“Rotated Digits” is a problem where we need to find how many numbers between 1 and a given value N are valid when rotated 180 degrees. A number is considered valid if it becomes a different number and still remains a valid number. The valid numbers after rotation for this problem are 0, 1, 8, 2, 5, 6, 9 and invalid ones are 3, 4, 7.

Clarifying Questions

  1. Q: What range is given for N?
    • A: 1 <= N <= 10^4.
  2. Q: Is there any specific range or case considerations?
    • A: No specific ranges or corner cases, just ensure that the solution is efficient for the upper limit.

Strategy

We need to determine:

  1. If rotating each digit in the number results in a completely valid number.
  2. If the resulting number is different from the original number.

Steps:

  1. Create mappings for digits that transform correctly (0->0, 1->1, 8->8, 2->5, 5->2, 6->9, 9->6).
  2. Iterate through each number from 1 to N.
  3. Check if the number contains only valid digits.
  4. Check if the rotated number is different from the original.
  5. Count such numbers.

Code

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int rotatedDigits(int N) {
        unordered_map<char, char> rotate_map = {
            {'0', '0'}, {'1', '1'}, {'8', '8'},
            {'2', '5'}, {'5', '2'}, {'6', '9'}, {'9', '6'}
        };
        unordered_set<char> valid = {'0', '1', '8', '2', '5', '6', '9'};
        unordered_set<char> must_change = {'2', '5', '6', '9'};
        
        int count = 0;
        for (int i = 1; i <= N; ++i) {
            string str = to_string(i);
            bool is_valid = true;
            bool has_must_change = false;
            for (char ch : str) {
                if (valid.find(ch) == valid.end()) {
                    is_valid = false;
                    break;
                }
                if (must_change.find(ch) != must_change.end()) {
                    has_must_change = true;
                }
            }
            if (is_valid && has_must_change) {
                ++count;
            }
        }
        return count;
    }
};

int main() {
    Solution solution;
    int N;
    cout << "Enter the value of N: ";
    cin >> N;
    cout << "Number of valid rotated digits: " << solution.rotatedDigits(N) << endl;
    return 0;
}

Time Complexity

The time complexity is O(N * k), where N is the number to be checked and k is the number of digits in N. In the worst case, k is constant with the upper limit (around log(10^4) = 5), so the time complexity effectively scales with O(N). This is efficient enough given the constraints.

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