Problem link : https://mirror.codeforces.com/contest/1926/problem/D Submission : 247469924
My Approach Here I tried to make the groups of 2 integers whose xor will be 0. If we consider number of bits=3 then max possible number in binary = 111(7) and after flipping the bits it will be 000(0). lets take a number 101(5) after flipping bits it will be 010(2) (as we are considering only 3 bits) then i concluded to get the number after flipping the bits we should do (maxPossibleNumber — currNumber) -> this gives the number after flip. In the same way I formed the groups for 11 bits maxnum=2147483647 for the given problem. But im getting TLE for this code. But unable to figure out why im getting TLE.Even though it is an O(N) approach. Please help me out in this.
Used a map and it got accepted 247485674. Maps are faster than unordered maps. Worst case of insertion in an unordered map is $$$O(N)$$$
unordered_maps are usually faster than maps, but they have some drawbacks:
However, unordered_maps are still useful in some scenarios where speed matters and hash collisions are unlikely or impossible. For example, on LeetCode or when dealing with permutation arrays, you can use unordered_map without worries.
Your approach is very right the only thing is that u have used an unordered_map which is very slow in searching just use map instead of unordered_map it will get accepted.
Here is the submission id for modified version of your code : 247486165
Same I also got TLE because of unordered_map as ai can range upto 2^31 which is more than 1e5 and in worst case scenario due to collisions unordered_map can take O(n). So use map in larger range as it guarantees log(n) in worst case.
Got it. Thank you guys !!