NOTE:
- It is highly recommended to first just read the explanation of questions that you were not able to solve and then again try to solve that question without going through the solution and after that, if you get stuck in coding then you can see solutions to that question.
2. If you do not find a solution coded in your preferred language, it is always better to understand core logic and code it out yourself.
- As, this Contest was purely based on Bit Manipulation and it’s algorithms, so we hope that you solved all of the questions using the same.
Contest Link : Programmers Army Monthly Contest - Bit Manipulation Coding Competition | CodeChef
1. Magical Game:
Explanation : Just count the total number of set bits in the given number, if it is even then the number is magical else not
Solution In C++ : https://ideone.com/sZGHnQ
2. Chef Need Help:
Explanation : In this question, you need to answer ‘Q’ queries, and in each query, you need to calculate the xor value from 1 to the given number ( let’s say n )
The logic(or observation) for the calculation of xor is as below:
if (n % 4 == 0) return n;
if (n % 4 == 1) return 1;
if (n % 4 == 2) return n + 1;
else return 0;
Solution In C++ : https://ideone.com/n2vu3E
3. Help Bob!:
Explanation : We are given an array B which is actually a prefix xor of array A.
To find the original array A, we can just do something like this:
We know that
A[0] = B[0]
A[0] ^ A[1] = B[1]
A[0] ^ A[1] ^ Ar[2] = B[2]
Hence, B[0]^B[1] => (A[0] ^(A[0] ^ A[1] ) ) = A[1]
B[1]^B[2] => ( (A[0] ^ A[1] )^(A[0] ^ A[1] ^ Ar[2] ) ) = A[2]
Similarly for upto the length of array.
Therefore, after calculating array A we can easily find out whether the Kth bit is set or not.
Solution In C++ : https://ideone.com/rxceAQ
4. Solve This:
Explanation : In this question, you are given ‘q’ queries, and in each query you will be ‘l’ and ‘r’ as a range, and you need to tell cumulative ChefItUp value of that range.
The ChefItUp value is defined as the total number of positive integers k such that 0 <= k<= n ( where ‘n’ is ball value and it will be unique ), and addition of n, k is same as xor of n, k.
Concept : We know that (n+i)=(n^i)+(n&i)
So n + i = n ^ i implies n & i = 0
Hence our problem reduces to finding values of i such that n & i = 0.
How to find count of such pairs? We can use the count of unset-bits in the binary representation of n.
For n & i to be zero, i must unset all set-bits of n. If the kth bit is set at a particular in n, kth bit in i must be 0 always, else kth bit of i can be 0 or 1
Hence, total such combinations are 2^(count of unset bits in n)
For example, consider n = 12 (Binary representation : 1 1 0 0).
All possible values of i that can unset all bits of n are 0 0 0/1 0/1 where 0/1 implies either 0 or 1. The number of such values of i are 2^2 = 4.
so, in this way you can calculate ChefItUp values efficiently, and after that you need to store this values in prefix sum array, so that you can answer queries in constant time.
Solution In C++ : https://ideone.com/a9CmI3
5. Impossible One:
Explanation : As there were some errors in test cases for this question, we have removed this question from the contest page, Sorry for the inconvenience caused if any.
We hope you enjoyed this contest and learned something new from it, also we hope you will be more excited about such contests in the future also.
if you have not joined our community yet, why you are waiting to meet amazing coders, great community support, and much more…
join our community on discord here : [ Programmers Army (discord.com)]
Make sure to fill the feedback form, as this is the only way we can work upon our improvements (if any needed) :
Copy of Programmers Army Monthly Contest - Bit Manipulation (Feedback) - Google Forms
See you at our next Monthly Contest !!
Happy Coding
Programmers Army 