shoaib98libra's blog

By shoaib98libra, history, 6 weeks 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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By shoaib98libra, history, 6 months ago, In English

I was working on a library called WhatsAlgo and needed 2 types of functionality:

  • generator: generates a bunch of test cases and creates one or more input files
  • validator: takes the solution file (could be in C++, Python, or other languages) and verifies it on each of the generated input files

This got me wondering, how do people generate test cases? I came across 2 popular platforms:

Are these the platforms used by the testers on CodeForces?

What about other platforms like AtCoder, HackerRank, LeetCode, or even Google?

I'd appreciate it if someone shed some light on this as it would help me a lot. Thank you all for your help!

Read more »

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

By shoaib98libra, history, 9 months ago, In English

I was trying out a problem (irrelevant) on LeetCode1372. Longest ZigZag Path in a Binary Tree. I posted this question on the forum but got no reply. Hence, I am asking the same question here.

I noticed some weird behaviour when using the max function. I took a max in two ways:

Solution 1: max(1 + a, 1 + b)

Solution 2: 1 + max(a, b)

Both of these do exactly the same task of getting the 1 + max. However:

The full code is also given below:

Solution 1
Solution 2

The details for Solution 1 are given below:

  • Runtime Error Message: AddressSanitizer: stack-overflow on address 0x7ffee1685ab8 (pc 0x7f4840414c34 bp 0x7ffee1686300 sp 0x7ffee1685aa0 T0)
  • Failed Input

If you notice, the code for both of them is exactly the same except for line 13. Could someone please tell me why Solution 1 fails? It really makes no sense to me.

Thank you for all your help!

Read more »

 
 
 
 
  • Vote: I like it
  • +41
  • Vote: I do not like it

By shoaib98libra, history, 11 months ago, In English

I was trying to solve the following problem (irrelevant): 1281C - Cut and Paste and I noticed something interesting. I inserted into the end of deque in two ways:

Solution 1:

n = d.size();
for (int k = 0; k < n; k++)
    d.push_back(d[k]);

Solution 2:

n = d.size();
d.insert(d.end(), d.begin(), d.begin() + n);

Both of these do exactly the same task of copying all the elements of the deque towards the end. However:

Diagnostics for Solution 2

The code for both of them is exactly the same besides the above mentioned lines.

Could someone please tell me why Solution 2 fails? Is it because the time complexity of insert in deque is worse than push_back for all elements? Does this mean you should never use insert with deque?

Thank you for all your help.

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By shoaib98libra, 22 months ago, In English

I was trying to solve the following problem: 1106B - Lunar New Year and Food Ordering and I noticed something interesting. Below are two solutions:

Solution [1]
Solution [2]

Both the solutions are pretty much the same except Solution [1] uses a function call findCheapest and Solution [2] has the raw code replacing the function call. However, Solution [1] causes a TLE on test 9 taking 2000 ms whereas Solution [2] gets accepted and takes 140 ms. This means Solution [2] is atleast 14× faster than Solution [1].

At first I thought the priority_queue might be causing some issues. But I am passing the address as you can see, so the function should be modifying the same location.

I always thought function calls do not affect the running time much. Does this mean function calls play a big role in the running time? Could someone explain to me why this could have happened?

P.S. I am pretty much a noob so please feel free to correct anything and sorry for any stupid mistakes.

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it