 # EQUALISE - Editorial

Author: Utkarsh Gupta
Testers: Nishank Suresh, Nishant Shah
Editorialist: Nishank Suresh

851

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')


It can also be proved that A and B can be made equal only when:

Let’s say A is the greater element and B is the smaller one then we need to check for only two conditions:

1. The remainder of A % B is 0
2. The remainder is an integer number with base 2

My solution snippet:

int big = max(a, b);
int small = min(a, b);

if ((big % small == 0) and (((big / small) & ((big / small) - 1)) == 0))
cout <<  "YES";
else
cout << "NO";