I faced this question among the challenges in another platform. I was unable to optimise my solution for this problem with it's constraints to pass within the time limit during the contest. The contest has ended and I feel it's time to learn.

Question :

You're given an array of size N. You need to generate all subsets for the given array. For each subset you need to OR it's minimum and the maximum element and add it to the result. You need to finally output the result after performing the mentioned operation for all it's subsets. Since the result can be large, output the result MOD by (10^9)+7.

Constraints :

1<=N<=(2*(10^5))

Let Ai be the values of the array where 1<=i<=N

1<=Ai<=1000

My Approach :

Since the problem demands to OR the minimum and maximum of each subset, I started by sorting the given array. Since the minimum element would have to appear with all the higher elements it pairs with, and the second minimum element would have to pair with all elements higher than itself and so on, sorting the array seems to be a correct approach towards the goal.

Over the sorted array I run my logic which is displayed in the below code snippet.

long MOD = 1000000007l;
long result = 0l;
for (int i=0;i<N;i++) {
    for (int j=i;j<N;j++) {
        if (i==j) {
            result = (result+array[i])%MOD;
            continue;
        }
        int OR = array[i]|array[j];
        result = (result+((OR%MOD)*(fastExponentiate(2,j-i-1)%MOD)))%MOD;
    }
}
print(result)

This looks good as an optimised brute solution running at O((N^2)*log(N)). Still not good enough to pass the time limit of 1 sec. I think the key idea lies somewhere in using the value's maximum limit of 1000 which is 10 bits for each number of the array. I tried several ideas but they were a catastrophe. I still couldn't optimise the logic. Can anyone help me if you've come across this type of problem ?

I got this question in one of my interviews. Let me state the problem statement clearly,

"You're given an undirected weighted graph consisting of N nodes and E edges and all the weights are unique ( meaning no weights will have duplicates ). Note the graph may also be disconnected ( there could be more than one component in your graph ). The nodes in the graph are labelled starting from 1 to N."

Now you're given an operation that you could perform which is, cut( u , v ) , where u is the label of one node and v is the label of another node and u < v . what this operation returns as result for the given u and v is that it takes the minimum weighted edge adds its value to result and then removes it from graph and then checks whether u and v are disconnected if they are disconnected it stops and returns the result. If the u and v are still connected by some means then it checks for the next minimum weighted edge in the graph and adds its value to the existing result value and removes the edge from the graph and then again check whether u and v are disconnected, if disconnected it stops and returns result. If not then again it continues the same procedure with the next minimum weighted edge in the graph.

So now the question is calculate the sum of all cut(u,v) for all u and v pairs in the graph where u < v . Like if N = 3 and say E = 5, (1,2), (1,3), (2,3) will be the all possible (u,v) pairs where u < v, where u and v are labels of the node. Then final SUM = cut(1,2)+cut(1,3)+cut(2,3). As the answer might be big MOD the value with 1e9+7.

So this is the question I got in my interview and I didn't have enough time to process this question and it seemed pretty hard too. And when I asked for hint, use disjoint set data structures was the reply. I had no clue on how to proceed it further. Can some body provide ideas and different approaches that could be taken to solve this problem.Thanks.