EQUALISE - Editorial

editorial
,
1

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

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";