# PROBLEM LINK:

**Setter:** Pritom Kundu

**Tester:** Teja Vardhan Reddy

**Editorialist:** Teja Vardhan Reddy

# DIFFICULTY:

Easy Medium

# PREREQUISITES:

Linearity of expectation, Probability

# PROBLEM:

Given n numbers (b_1,b_2,....b_n) and probabilities of choosing each of the numbers. Find the expected xor value of the chosen set.

# EXPLANATION

Let X be the random variable representing xor of chosen set. And x_i be random variable representing i th bit in xor of chosen set.

X = \sum_{i=0}^{30} 2^i * x_i

Now E[X] = E[\sum_{i=0}^{30} 2^i * x_i]

E[X] = \sum_{i=0}^{30} E[ 2^i * x_i] (By linearity of expectation).

E[X] = \sum_{i=0}^{30} 2^i * E[x_i]

We are only considering first 30 bits (infact log_2(max_{i=1}^n b_i) \lt 30 from given constraints) because for all other values of i, each of the n inputs always takes a value zero for that bit, hence that bit of xor of chosen set will be always zero.

Now, let us focus on how to calculate E[x_i].

Let us iterate numbers from 1 to n and consider whether they join the set or not (Assume j th number joins set with probability p_j).

Initially before we start, P_0[x_i = 0] = 1.

Now for j th number,

**Case 1:** i th bit is zero.

Irrespective of we take it into the set or not, it wont affect x_i.

Case 2: i th is one.

Now, we consider both cases that j th number is in set and not in the set and compute the probability.

P_j[x_i = 0] = P_{j-1}[x_i = 0]*(1-p_j) + P_{j-1}[x_i = 1]*(p_j)

P_j[x_i = 1] = 1 - P_j[x_i = 0] (since x_i must be either zero or one)

And finally E[x_i] = P_n[x_i = 1]

So now, we can compute E[X] from above derived formula after we know E[x_i].

# TIME COMPLEXITY

To compute E[x_i] for each i, we need O(n) time.

Hence, total time needed to compute E[x_i] for all i is O(n* log_2(max_{i=1}^n b_i)).

Now to find E[X] given all values of E[x_i] takes O(log_2(max_{i=1}^n b_i)) time.

Hence total time complexity is O(n* log2(max_{i=1}^n b_i)).

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N = 1e5 + 7;
const int K = 30;
int a[N];
double p[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while (t--) {
int n;
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
for (int i=1; i<=n; i++) cin>>p[i];
double ans = 0;
for (int i=0; i<K; i++)
{
double prob = 0;
for (int j=1; j<=n; j++)
if (a[j] & (1<<i))
prob = prob * (1-p[j]) + (1-prob) * p[j];
ans += prob * (1<<i);
}
cout<<setprecision(15)<<fixed<<ans<<"\n";
}
}
```

## Tester's Solution

```
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int a[123456];
long double p[123456];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i,j;
rep(i,n){
cin>>a[i];
}
rep(i,n){
cin>>p[i];
}
long double zer,one,ans=0;
rep(j,30){
zer=1.0;
one=0.0;
rep(i,n){
if(a[i]&(1<<j)){
zer=zer*(1-p[i])+one*p[i];
one=1-zer;
}
}
ans+=one*(1<<j);
}
cout<<setprecision(35)<<ans<<endl;
}
return 0;
}
```

Feel free to Share your approach, If it differs. Suggestions are always welcomed.