Loading web-font TeX/Math/Italic

Problem #150

Fun with Expectation

Consider an array of n numbers where each element can be any non negative x bit number ( 0 to 2^x - 1 ) with equal probability. Let F(n,x) be the expected value of the sum of bitwise xor of all possible subsequences of the array.

Eg. Consider the array {1,2,3} .

Sum of xor of all possible subsequences of this array = 1 + 2 + 3 + 1^2 + 1^3 + 2^3 + 1^2^3 = 1 + 2 + 3 + 2 + 1 + 3 + 0 = 12.

Note: ^ is the bitwise xor operation here.

F(2,2) = 4.5

Enter your answer as floor( F(29,30) + F(30,29) ) .

Contributed by Saharsh Luthra

Solved by 37 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.