slowerThanSnail's blog

Count no. of subsets having xor k
By slowerThanSnail, history, 5 years ago, In English

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 ?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you describe how to find the number of subsets having xor less than k with example.

    → Reply