PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Utkarsh Gupta
Testers: Nishank Suresh, Nishant Shah
Editorialist: Nishank Suresh
DIFFICULTY:
851
PREREQUISITES:
None
PROBLEM:
Chef has two numbers A and B. In one move, he can multiply one of them by 2. Is it possible to make both of them equal?
EXPLANATION:
Without loss of generality, let A \leq B.
Note that if it is possible to make A and B equal, this can always be done by only multiplying A by 2 several times, and never touching B.
Proof
Suppose we perform the operation x times on A and y times on B, where x, y \gt 0. Then, if they are equal in the end, they will also be equal if we had performed x-1 and y-1 operations respectively.
Reducing the number of operations by 1 like this can be done till y becomes 0.
This gives us a simple solution:
- While A \lt B, multiply A by 2.
- Now, suppose we reach A \geq B.
- if A = B, the answer is “YES”
- If A \gt B, the answer is “NO”
There are also other ways to solve the problem, for example:
- While A is even, divide it by 2
- While B is even, divide is by 2
- At the end, if A = B the answer is “YES”, otherwise the answer is “NO”.
TIME COMPLEXITY:
\mathcal{O}(1) per test case.
CODE:
Editorialist's Code (Python)
for _ in range(int(input())):
a, b = map(int, input().split())
if a > b:
a, b = b, a
while a < b:
a *= 2
print('yes' if a == b else 'no')