Count no. of subsets having xor k
Difference between en2 and en3, changed 0 character(s)
Hi everyone, recenetly there was a hiring [challenge](https://www.hackerearth.com/challenges/hiring/jpmc-se-2019/) by JP Morgan on HackerEarth, and this problem was there. <br> ↵
**Problem statement :** <br>↵
Given an array of N integers and an integer k, <br>↵
let cnt1 = no. of subsets of array whose XOR is less than k, <br>↵
    cnt2 = no. of subsets of array whose XOR is equal to k, and <br>↵
    cnt3 = no. of subsets of array whose XOR is greater than k. <br> <br>↵
↵
You have to print value of expression : (cnt1 * cnt2) + (cnt2 * cnt3) + (cnt3 * cnt1) &mdash; (cnt1 + cnt2 + cnt3)<sup>2</sup> . <br> <br>↵
**Constraints :**  <br>↵
1 <= N, k, A[i] <= 100000.↵
↵
<br> ↵
There is O(maxVal * N) [solution](https://www.geeksforgeeks.org/count-number-of-subsets-having-a-particular-xor-value/) but obviously  it's not feasible for given constraints. How to solve it with better time/space complexity ?  <br>↵
**Edit:** We had to print exp % 10<sup>9</sup> + 7.

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)