CareerCup

How about do the "dividing" part of quicksort with the value 0 as the pivot. All values lesser than 0 will be on left and values greater than 0 will be on right.

Takes O(n) time.

Not sure about whether the relative positions are maintained.

Naive complexity would be n!

We could reduce the complexity via dynamic programming. Store the lesser components, so that you don't have to permute them again.

For example, if I have already permuted {abc} then I don't have to entirely permute {abcd}.

The numbers do have sematic meaning, eg: location. Hence, if the database is distributed, that helps. Additionally, the DB must be stored in a N-nary search tree where N is large, reducing the height of the tree significantly.

Will it work for a1 = {aab} and a2 = {ab} ?

Lets say a1 = {0,0} a2 = {1,1} XORs will be same, right?

@neo, theoretically, the rime numbers should be already populated. Since number of numerics are fixed and independent on length of string, theoretically, its O(1). The runtime of algorithm, theoretically is O(n). But yeah, practically infeasible.

Isn't this of n log n complexity? OP has asked n complexity

We can maintain a cumulative array from the begining. Let it be c[].

Then, summation(a[i]...a[j]) will be c[j] - c[i].

So you mean like this?

Start with the center-most element. Top-left sub-matrix is definitely lesser than center while bottom-right is definitely larger than center.

Make a comparision and eliminate one of them. You will have 3 submatrices remaining. Recursively call on them.

Is there anything better than this? I was thinking in terms of deterministic kth median finding algorithm.

Any power of 2 i = 100000.....
i-1 = 011111...

Thus, i&(i-1) = 00000.....