I submitted this https://www.codechef.com/viewsolution/40092910 solution which is O(N^2 )
and still it passed all the TCs even though N is 10^5.
Later on, I optimized it with a Queue solution https://www.codechef.com/viewsolution/40107816 which is O(32*N) and surprisingly it ran slower than the N^2 solution. Can anyone confirm is it just weak TC or something else?
This happend with me too, but I think in your O(N) approach the push and pop operations are quite costly, so the constant of multiplication may be quite big ( of order log(n)) . But in your O(n^2) approch , you are doing only bitwise operations, only. Further, in O(n^2), the second loop tool has a break condition. so it may not be even completing o(n^2) operations
Firstly your code in the first link is not N^2 solution (not exactly). The time complexity for that is a lil tricky.
The first thing to notice is that, the numbers can only be under a 32 bit signed integer. So when you’d loop through each number, and then each number is being tested for it’s 32 bits. When you find a set bit (say kth bit is set), you’re looping through numbers from i to n -1, where possibility of finding a number with kth set bit need not travel till end of the array (unless for one tricky test case, [1, 2, 4, 8, 16, ...........2^{30}] and that too has a length of only 30). So finding the next element with kth set bit can be found in less than N iterations. So your code is not actually O(N^2) but simply O(32*N). Hope you understood.
Yes I understand that but this just means that the sequence of integers in input were not much spread out in terms of bitcount. N^2 solution relies on finding the next closest element with the same set bit, its just maybe finding it without iterating much and hence, the TCs were weak I thought.
Thanks a lot!! I get it now.