### slowerThanSnail's blog

By slowerThanSnail, history, 15 months ago, 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 % 109 + 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 ? Comments (6)
 » 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).
 » 15 months ago, # | ← Rev. 3 →   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.