shoaib98libra's blog

By shoaib98libra, history, 9 days ago, In English

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
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

let's take 2581 for example now we calculate possible numbers without involvement of invalid numbers,

So, fixing 2,5,8 we have (1,0) at 1's place = 2 numbers.

Now, fixing 2,5 we have (6,5,2,1,0) available at 10's place and corresponding to each of them we have (9,8,6,5,2,1,0) at 1's place so we get 5*7=35 numbers.

Now, fixing 2 we have (2,1,0) at 100's place available and corresponding to it we have 7 numbers at 10's place and 7 at 1's place so we get 3*7*7= 147 numbers. Now, for 2 we can put (1,0) and corresponding to it 7 numbers will be available at each unit place so, we get 2*7*7*7= 686 numbers.

On adding we get 870 numbers.

Now we should have at least 1 valid digit in each number.

So, we form numbers with digits 1,0,8 less than given number itself and subtract from given number(because we have formed all numbers less than given number using 9,8,6,5,2,1,0, so on removing numbers formed by only 1,0,8 we will have numbers which at least have 1 valid digit).

For 2581 in place of 2 we can use (1,0) which gives us option of putting all three(1,0,8) at remaining 3 places. So, total numbers =2*3*3*3= 54

On subtracting 870-54= 816 which is required number.

Note: if the number itself contains invalid digit(not at 1's place) then as we had (1,0) in 2581 we can have all 7 at 1's place.

time complexity is O(log(N)). You can try this approach on 235 for better understanding . Hope it helps .