PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
You are given two arrays A and B, of size N. In one move, you are allowed to swap the values of A_i and B_i for any i. Determine the maximum possible bitwise AND of array A, and the minimum number of moves needed to achieve it.
EXPLANATION:
Observation: The x^{th} bit (in the binary representation) of the final answer is 1 if and only if, the x^{th} bit is 1 in each of the upward facing numbers.
(The proof is a direction application of the definition of bitwise AND)
Define an array S such that, s_i is
- 0, if in the final answer, card i should have number A_i upwards,
- 1, if in the final answer, card i should have number B_i upwards,
- -1, if the side of the card to be facing up is undecided (the default state of the card in this case is number A_i upwards).
initially, all s_i is -1.
Let us tackle the problem one bit at a time. Since we are concerned with maximising the answer, we seek the most significant bit to be as large as possible.
Iterate over the bit range in descending order - from 29 to 0 (largest and smallest possible bits that can be set in the answer, respectively). Let the current bit we are processing be x.
Step 1: Determine if it possible to flip a subset of the undecided cards (those with s_i = -1) such that every number facing upwards has the x^{th} bit set.
Why? How?
By the definition of s_i, it is clear that, the only cards we can flip are those whose state is undecided. To determine if it is possible to have all upward facing numbers with the x^{th} bit set:
- check if the x^{th} bit is set in the upward facing number of each decided card.
- check if the x^{th} bit is set in either A_i or B_i of each undecided card.
This can be accomplished easily using bit manipulation (the x^{th} bit is set in number a only if a\&2^x \ne 0).
Step 2: If possible, flip the bare minimum number of undecided cards to achieve the same.
How?
By the definition of bitwise AND, it is clear that each upward facing number must have the x^{th} bit set. Thus, iterate over each of the N cards,
- skipping the cards whose state is already decided.
- skipping undecided cards with both A_i and B_i having the x^{th} bit set.
- setting the final state of the remaining cards such that, in the upward facing number, the x^{th} bit is set. Also, update the values of s_i appropriately.
At the end, the maximum possible answer is the bitwise AND of all upward facing numbers (use the number A_i if s_i equals -1) and the minimum number of cards to flip is equal to the number of cards with s_i=1.
TIME COMPLEXITY:
For each valid bit, we iterate over the N cards twice (once per step). We also iterate over the N cards one last time to determine the answer. The total time complexity is then:
where d, the bit range, is 30.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters