[LeetCode] Rotated Digits

788. Rotated Digits

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

  • Time : O(7log10n)
  • Space : O(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int rotatedDigits(int n) {
vector<int> candidate1 {0,1,8};
vector<int> candidate2 {2,5,6,9};
queue<pair<int, bool>> q;
int res = 0;
for(auto c : candidate1) {
if(!c or c > n) continue;
q.push({c, false});
}
for(auto c : candidate2) {
if(!c or c > n) continue;
q.push({c, true});
}

while(!q.empty()) {
auto [target, verify] = q.front(); q.pop();
if(verify) res++;
for(auto c : candidate1) {
int nxt = target*10 + c;
if(nxt <= n)
q.push({nxt, verify});
}
for(auto c : candidate2) {
int nxt = target*10 + c;
if(nxt <= n)
q.push({nxt, true});
}
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/19/PS/LeetCode/rotated-digits/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.