10

Moderator's note: this is an on going contest problem. Per usual protocol the answers have been hidden and the question is locked until the end date of the contest. (21.03.2014)

Given a list containing N integers, How to find the XOR_SUM of all the non-empty subsets of the list.

E.g. XOR_SUM of list A having three elements {X1, X2, X3} can be given as follows. All non-empty subsets will be {X1, X2, X3, (X1,X2), (X2,X3), (X1,X3), (X1,X2,X3)}

XOR_SUM(A) = X1 + X2 + X3 + X1^X2 + X2^X3 + X1^X3 + ((X1^X2)^X3)

EXAMPLE : Let N=3 and list be [1,2,3] then here answer will be 12 as Their will be 7 non-empty subsets whose XOR is given below

1 = 1
2 = 2
3 = 3
1^2 = 3
2^3 = 1
3^1 = 2
1^2^3 = 0

So sum of all such XORs will 12.

Willie Wong
  • 73,139
user3001932
  • 1,056
  • it works well if any number in set is even but if set consists of only odd numbers like 3 ,5 then it fails –  Mar 18 '14 at 15:46

1 Answers1

19

Consider one bit position at a time. How many of the terms have bit $i$ set? The terms that have bit $i$ set are exactly those that correspond to a subset that contains an odd number of inputs that have bit $i$ set.

  • If there is any input that has bit $i$ set, then exactly half of the $2^N$ possible subsets will be of this form, and so they will contribute $2^{N-1+i}$ to the final sum.

  • On the other hand, if no input has bit $i$ set, then of course no terms will have that bit set either.

Summing these contributions of $2^{N-1+i}$ per bit position is easy enough -- the final sum will simply be $2^{N-1}$ times the bitwise OR of all the inputs.

hmakholm left over Monica
  • 286,031
  • So basically the solution for a given set x1,x2,x3,x4...xn is : (x1 | x2 | x3 |x4 |...xn ) * ( 2^N-1) ; But this is not working for all the test cases in a challenge ..?? Any suggestion why – prateeak ojha Mar 16 '14 at 22:24
  • 1
    @prateeak: Yes, that's what the answer ought to be. What do you men by "not working" -- are you using too small ints to hold the result, perhaps? – hmakholm left over Monica Mar 16 '14 at 22:57
  • @HenningMakholm The concept is perfectly working. No doubt, I coded and got Accepted. But I didn't understand you explanation clearly. Sir. Can you write a little more on it? An example will be appreciated :) – Kaidul Islam Mar 20 '14 at 05:26
  • @KaidulIslamSazal: Which part of the explanation is unclear? – hmakholm left over Monica Mar 20 '14 at 13:34
  • The part you said "The terms that have bit i set are exactly those that correspond to a subset that contains an odd number...". Also can you Please explain x1=1, x2=2 and x3=3 with your idea? – Kaidul Islam Mar 20 '14 at 17:50
  • 1
    Temporarily deleting this answer as it is from an on-going programming contest. – Willie Wong Mar 21 '14 at 10:01
  • 1
    Hi Henning Makholm, thanks for detailed explanation, however I have a doubt ....ORing the number will give you all possible 1 positions in that column so you get all possible 1 positions in all the columns. I also got that only half of the subsets will have some particular bit position set to 1, but why multiplying this OR of all numbers with half the number of subsets will give you answer? – codeomnitrix Sep 05 '15 at 05:26
  • 1
    @codeomnitrix: Because you're adding the XORs from each subset. Half of the subsets will contribute one copy of that bit to the final sum. – hmakholm left over Monica Sep 05 '15 at 13:48