PROBLEM LINK:
DIFFICULTY:
Cakewalk
PREREQUISITES:
Bit Operations
PROBLEM:
Potter has got multiple boxes. Each box has a torch which is either on or off. Similarly each box can have a magic wand, which if used can turn the torch on. For example:
Box1 Box2 Box3
1 1 0 (Torches)
0 1 1 (Magic Wands)
In the first and second box there is no need for a magic wand, the torches are already on, in the third box, the torch is initially off so we can use the magic wand to turn the torch on. The boxes are represented in the form of a decimal number, whose binary representation (each bit will represent one box) will give the current state of torches and wands in each box.
For each box Potter wants to know whether it can emit light or not, representing the status by 1
if it can, or 0 if it can’t. Help Potter by giving a decimal representation of the final state of all the boxes.
QUICK EXPLANATION:
Take bitwise or ( | ) of two numbers in input and print it.
EXPLANATION
We are given one bitmask representing all the torches’ states A. This means that ith bit of the given number A represents the state of i_{th} torch (1 if it is lit and 0 otherwise).
There’s another bitmask B representing whether we can light i_{th} torch. The story is similar to the first mask A, i_{th} bit is set to 1 if we can light the i_{th} torch, and 0 otherwise.
By checking simple cases we conclude:
- Lit torches are never affected
- Non-lit torches are affected only if we can light them
We can translate this to bitwise operations, suppose * is the operation we apply, we see that:
- 1 * 1 = 1
- 1 * 0 = 1
- 0 * 1 = 1
- 0 * 0 = 0
In other words, * behaves juts like bitwise or ( | ), and as we are required to print resulting mask in integer form, we can simply print the bitwise or of the numbers in input - A | B.
SOLUTIONS:
Alternate Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int t; cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
cout << (a | b) << '\n';
}
return 0;
}