Count the number of subsets of the sequence 1,2,3,4,5...(up to n) such that the XOR of all elements of the subset is an odd number

Question

Count the number of subsets of the sequence 1,2,3,4,5...(up to n) such that the XOR of all elements of the subset is an odd number.

for eg: for a sequence 1,2,3.

the answer will be: 4

(1},{3},{1,2},{3,2}

Answer 1

Subset should contain an odd number of odd numbers, because you only care about last bit, for example:

1 2 3 4 5 
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101

{1} {3} {5} - cause those have '1' as last bit itself.

subsets above with any combination of even numbers:

{1,2,4} {1,2} {1,4} {3,2,4}... so another 9 subsets
{1,3,5} is an odd also.
and variation with even numbers: {1,3,5,2} {1,3,5,4} {1,3,5,2,4 }

so answer is 16. it has nothing to do with c++

You have to count all possible combinations of even numbers in sequence(use combinatorics, order doesn't matter) + 1(when zero even numbers used). Count all possible sequence of odd numbers(order doesn't matter). Multiply result.

1 2 3 4 5
{2} {4} {2,4} {} = 4 options
{1} {3} {5} {1,3,5} = 4 options
4*4 = 16

Answer 2

A number is odd iff the last bit is set. We can use this observation as follows:

Start by separating the numbers into even and odd numbers. Obviously, there will be e=floor(n/2) even numbers and o=n-e odd numbers.

The choice of even numbers does not affect the oddity of the result. Hence, you can use any combination. There are n_e = 2^e such combinations (where ^ is the power operator).

From the remaining odd numbers, you have to choose an odd number. The number of combinations is n_o = 2^(o-1).

In total, you have n_e * n_e = 2^e * 2^(o-1) = 2^(e + o - 1) = 2^(n - 1) combinations.

Answer 3

First, we know all even numbers end with 0 (bitwise) and all odd numbers end with 1

So it means only odd number XOR even number will give us an odd number.

Consider a set with m even numbers and n odd numbers,

As XOR is commutative and associative, the order of the XOR is not important, and which we can observe the following:

1. We need odd number of odd numbers (need at least one, and they will give us an odd number when XOR each other)

2. The number of even numbers has NO effect to the answer (we can pick any number of even numbers possible, even 0, and they will give us an even number when XOR each other)

Combine 1 and 2, we will get an odd number when XOR the whole set.

Now, how many combinations are there?

Let m be the total even numbers, and n be the total odd numbers

For 1, there are M = mC1 + mC3 + mC5... = 2^(m-1) choices

For 2, there are N = nC0 + nC1 + ... = 2^n choices

So the answer is M*N = 2^(m+n-1)

Note that m+n = Your integer range, so it can further be simplified to 2^(size-1)

For example: {1,2,3,4,5}: m =2, n=3, so answer is 2^4 = 16