Q1. What would be the time complexity to find intersection of two SORTED ranges or arrays?
Which data structure or STL container would give the best time complexity?
Q2. Does O(n2 * log©) pass in 2 seconds time limit? n = 10^5
1 Like
Heya!
For your first question, you can use a simple function included in STL. [set_intersection][1] will do the work. You just need two vectors and then sort them and then use this function right away! I wonder how much easy it is to do all these things anyways.
Approach2:
There are many other ways to do this thing. You can use simple hashing or map for the same. Just have a count of the frequency of element in both the arrays and see if any element appears more than once.
Now for your second query, It depends. It depends on your program and the constant factors but anyway on a normal judge, we assume that 10^6 operations can be done under a second to be on the safer side always. If you just run a for loop 10^8 times without anything inside it then it can run in under a second sometimes but other operations like modulo,division are costly but here you are off by a large number. As you have not specified what is c I will try to neglect it and then you have an upper bound of O(10^10) which is like 1000 times 10^6 so it will run for around 16 minutes which is clearly not good.
Feel free to ask something more!
[1]: http://en.cppreference.com/w/cpp/algorithm/set_intersection
1 Like
Computer science is a very vast topic,wedding photography abu dhabi and like this article so much.Programs are neede in this field and it is very good.