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 ?
