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