Count no. of subsets having xor k

Revision en4, by slowerThanSnail, 2019-10-26 20:03:35

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 ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English slowerThanSnail 2019-10-26 20:03:35 261 Tiny change: '\n**Edit 2 : ** Seems l' -> '\n**Edit 2:** Seems l'
en3 English slowerThanSnail 2019-10-26 19:18:08 0 (published)
en2 English slowerThanSnail 2019-10-26 19:17:26 58 Tiny change: 't:** We have to print ' -> 't:** We had to print ' (saved to drafts)
en1 English slowerThanSnail 2019-10-26 19:15:08 939 Initial revision (published)