Exist or Not Hashing

#1

Getting TLE in one of the test cases.
Here is the code https://ide.codingblocks.com/s/99035

#2

It is because m.find() operator is taking O(logn)
where n is the no. of elements in the map.

your code is using nested loops:
while(t–){ // O(t)
while(q–){ //O(q)
m.find() //O(log(n))
}
}

Thus, total time complexity is coming out to be : O(t.q.log(n))
Hence, it is causing TLE.

Try to solve it using another efficient approach.
Hope, this would help.
If you still have doubts, feel free to ask.

#3

I have used map instead of unordered_map because in worst case unordered map takes O(n), but map takes just O(logn). Moreover with every test case the number of queries vary, so what else can i do if not using while loops for each test case and query.

#4

Your code is showing unpredictable behavior for second test case.

Do the following modification, and your code will work perfectly:
while(q-- > 0){}

Hope, this would help

1 Like
#5

I checked the test cases.
In the second test case, the value of q is negative.

Give a like, if you are satisfied.

1 Like