Question: Rotated Digits

Revision en2, by shoaib98libra, 2020-10-17 18:21:15

I read the following question: LeetCode — 788. Rotated Digits. The same question is mentioned below.

Rotated Digits

X is a good number 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. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other (on 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.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:
Input: 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 rotating.

It's pretty easy to come up with a solution that works in O(N • log N) time:

int rotatedDigits(int N) {
	int cnt = 0;
	for (int i = 1; i <= N; i++)
		cnt += is_good(i);
	return cnt;
}

bool is_good(int num) {
	bool found = false;
	unordered_set<int> good = {2, 5, 6, 9};
	unordered_set<int> invalid = {3, 4, 7};
	
	while (num) {
		if (invalid.count(num % 10))
			return false;
		found |= good.count(num % 10);
		num /= 10;
	}
	
	return found;
}

But I am interested in knowing how to solve it faster, I think it can be done in O(log N) time. I believe you can do it faster using some Math, but it's hard for me to get the Math right.

Could someone please shed some light on how you could solve it faster? I have provided sample test cases at the end of this blog.

Thanks!

Sample Test Cases

Input: 10 90 100 200 235 258 2581 10000
Output
4
34
40
81
101
107
816
2320

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English shoaib98libra 2020-10-17 18:21:15 0 (published)
en1 English shoaib98libra 2020-10-17 18:21:00 1998 Initial revision (saved to drafts)