PROBLEM LINK:Author: Vitaliy Herasymiv DIFFICULTY:Medium. PREREQUISITES:Dynamic Programming PROBLEM:Given a set of integers $\{0, 1, 2, ..., n\}$, find the number of ways of choosing a subset of $k$ integers such that the xor of all chosen integers has exactly $B$ set bits(in the binary representation). EXPLANATION:In this problem, our approach will be to generate(smartly) all possible $k$ integers bit by bit from MSB in a particular order. At any step $i$ we will assume that we have generated $k$ integers upto ith bit following a order and extend it to i+1th bit( taking care of the ordering as well) and in the process, counting all possible ways of extension of $k$ integer. Now to smartly count all the ways we will use dynamic programming approach. Define a 3D dp matrix $\text{dp[i][b][mask]}$ which stores the number of ways of choosing $k$ integers of $i$ bits such that their xor has $b$ set bits and the $k$ integers follow a specific order according to the mask. Important idea to note here is that the $k$ integers chosen follow a specific order defined by mask as follows : 0th bit of mask is 1/0 iff 1st chosen integer is strictly less/equal than n upto i bits from MSB. This means that the $k$ integers are considered in decreasing order. Since the ordering doesn't matter in set, there is no harm in generating $k$ integer in decreasing order. Lets say the first $i$ bits of $k$ integers are already generated according to mask. Now these $k$ integers can be extended to $i+1$th bit(from MSB) in $2^k  1$ ways, that is the value of pred( it is a $k$ bit number such that $j$th bit of pred is $i+1$th bit of $j$th chosen number, refer to the figure below for more detail) can take $2^k  1$ value. And for each value of pred and old mask the ordering of $k$ integer ( also the mask ) will change. Note that the newmask (which denotes the ordering among k chosen number) may be invalid because there may be some pair(s) of numbers which are not in decreasing order, in that case the newmask will be invalid. Now lets consider each possible scenario case by case. First initalize newmask with mask. The first condition involves the number $n$ and the 1st chosen number. If 0th bit of mask is 0 which implies 1st number is equal to n upto i bits from MSB then The following condition involves j+1th and jth chosen number where j varies from 1 to k1. After the computation of newmask and it validity update the dp state dp[i+1][b+setBits(pred)%2][newmask] += dp[i][b][mask] if newmask is valid. Base case will be dp[0][0][0] = 1. Below is basic structure of the code for more clarity.
Now the final answer will be dp[31][B][2^k  1] + dp[31][B][2^k  2] corresponding to the case when 1st number is equal to n and when 1st number is strictly less than n. Refer to the tester's code for more details. The time complexity of the algorithm is $\mathcal{O}(B\log n2^k)$. Solution:Setter's solution can be found here
This question is marked "community wiki".
asked 21 Mar '15, 02:14
