I spent several hours trying to Hail XOR question from December Long Challenge. I am getting TLE in one test case. The complexity of my solution is O(32*N) yet the code is giving TLE for one case. Please help me in figuring out the reason. You can check my code - Here.
1 Like
Hello Sir, I believe your unordered map is giving TLE.Change it to ordered map
Try to submit same code in C++17 once.
Hello. I tried doing that but still didn’t get AC.
I tried this too. Still getting TLE for that case.
Try to do without maps.The problem doesnt need maps.Even if u do in a brute force manner, the solution will get AC
1 Like
The usage of maps in this solution can be the reason of the TLE as it makes the push pop operations costly.
This question can be done even by solution having O(N^2) complexity virtually considering the bitwise operations and proper break statements
which would effectively bring down the complexity to O(32*N) in practice.
And about language comparison C++17 is faster than C++14 , and same is the case with Pypy3 being faster than Python3.
Replaced the map and added a for loop to find the element and it worked. Why did this happen? Shouldn’t this be slower than having a map in my code?
Replaced the map and added a for loop to find the element and it worked. Why did this happen? Shouldn’t this be slower than having a map in my code? In the worst case, if I end up not finding a number with my MSB on, then I would have travelled the whole list again. So map would’ve optimised it. Also why is pushing and popping in a map so costly here? Its average case is O(1). I am literally shocked.
When you loop through each number, then each number is being checked for 32 bits only.If you travel from i = 1 to n-1 and find any bit as set then for possibility of same set bit in next number does not necessarily mean that you have to travel till the end unless a special case of 2^k, where k is also less than 30. So next element can be found in less than N iterations.
Regarding the solution using map, in this case the push and pop operations will be costly than the direct bit comparisons since the entire map structure with queue also has to be maintained, so using a map for this problem is not a good alternative. Hope you understood 
And this question can be done using the two loops approach even with directly using elements in original decimal form if the loops are handled carefully.
2 Likes
Maps have a complexity of O(log n) for deletion and insertion because they are non-linear data structure.
Yes, I get it. But if I take a very peculiar case, example N is 10^5 and the array elements are all 1’s except the first element in which all the bits are on except the odd bit. Something like this (11…110). So in this case I would iterate for all the bits that are on and in each case, I would search for an element having this bit on. Failing to find any such element. So I would iterate the whole array 30 times for the first element. After that finding, the next element would be easy no doubt. What would be the TC of such a case?