codejam 2014 bits xoring

Hey guys am not able to get the idea how to solve the first question
https://code.google.com/codejam/contest/2984486/dashboard#s=p0
of Codejam Round 1A,Pleae help me out…Thanx in advance :slight_smile:

Lets call the two sets of strings we have as given,reqd. Now if it is possible to get reqd from given then reqd[0] must be formed from either given[0] or given[1] … given[n-1].

Check for every value in given which all switches you need to flip to get reqd[0]. Now flip those switches for every value in given. If you get all the elements in reqd by flipping these switches then ans=min(ans,switches flipped).

To see which all switches are flipped you can take an XOR. A 1 will indicate a flipped switch and a 0 will indicate a non-flipped switch.

ans=1000000;
for(i=0;i<n;i++)
{
    string flip=XOR(given[i],reqd[0]);
    string temp[n];
    for(j=0;j<n;j++)
    {
        temp[j]=XOR(given[j],flip);
    }
    if(all elements of reqd are in temp)
        ans=min(ans,number of 1's in flip)
}

Now if ans is still 1000000 that means we haven’t found an answer so print not possible else print ans.

4 Likes

@akulsareen Thanx Yeah now got the concept :smiley:

//