I faced this question in one of challenges. I was unable to optimise my solution for this problem for it's constraints to pass within the time limit.

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 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.

                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). Still not good enough to pass the time limit of 1 sec. 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 ?