Hi everyone, recenetly there was a hiring challenge by JP Morgan on HackerEarth, and this problem was there.

**Problem statement :**

Given an array of N integers and an integer k,

let cnt1 = no. of subsets of array whose XOR is less than k,

cnt2 = no. of subsets of array whose XOR is equal to k, and

cnt3 = no. of subsets of array whose XOR is greater than k.

You have to print value of expression : (cnt1 * cnt2) + (cnt2 * cnt3) + (cnt3 * cnt1) — (cnt1 + cnt2 + cnt3)^{2} .

**Constraints :**

1 <= N, k, A[i] <= 100000.

There is O(maxVal * N) solution but obviously it's not feasible for given constraints. How to solve it with better time/space complexity ?

**Edit:** We had to print exp % 10^{9} + 7.

**Edit 2:** Seems like I wrote the wrong expression. It was reducible to (cnt1 + cnt2 + cnt3)^{2} as pointed out by navneet.h. Still is there any faster way to calculate count of subsets with xor k faster for given constraints ?

Auto comment: topic has been updated by slowerThanSnail (previous revision, new revision, compare).that question wasn't like that, the equation get reduced to something like (cnt1+cnt2+cnt3)^2 which is (2^(n-1))^2,i got ac on all test cases.

Yes.Unfortunately I could not identify the pattern. I'll update the blog. Thanks for solution though.

Auto comment: topic has been updated by slowerThanSnail (previous revision, new revision, compare).You can consider for every element a[i] in the given array its binary representation and apply an algorithm similar to gaussian elimination to get its row echelon form. After that, you greedily take or not take a number with respect to the need of having its most significant bit set / not set in k. If you cannot get xor equal to k than the answer is 0. Otherwise, the answer is 2 ^ p where p is the number of elements equal to 0 in the row echelon form of the array (because it doesn't matter if you take them or not because the xor of the values will not change). I hope this helps. If anyone sees any mistake in this solution, please tell me.

PS:This solves the"Edit 2"question.LE:You can solve for the number of subsets having xor less than k (or greater than k) by iterating over the prefix that you want to coincide with the prefix of k and setting the next bit to be different such that the relation between your xor and k is the one you want (< / >) (for example if you want "<" you change a 1 into a 0). After that, the rest of the bits don't matter so it is 2 ^ p where p is the number of elements remaining.can you describe how to find the number of subsets having xor less than k with example.