Count no. of subsets having xor k

Правка en3, от slowerThanSnail, 2019-10-26 19:18:08

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский slowerThanSnail 2019-10-26 20:03:35 261 Tiny change: '\n**Edit 2 : ** Seems l' -> '\n**Edit 2:** Seems l'
en3 Английский slowerThanSnail 2019-10-26 19:18:08 0 (published)
en2 Английский slowerThanSnail 2019-10-26 19:17:26 58 Tiny change: 't:** We have to print ' -> 't:** We had to print ' (saved to drafts)
en1 Английский slowerThanSnail 2019-10-26 19:15:08 939 Initial revision (published)